Guest User

Untitled

a guest
Dec 23rd, 2019
118
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.54 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4. #define int ll
  5. #define all int i=0; i<n; i++
  6. #define pb push_back
  7. #define pf push_front
  8.  
  9. #define FAST_IO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
  10.  
  11. int n;
  12. vector< pair<int, int> >v;
  13. map<pair<int, int> , int> cult;
  14. map<pair<int, int> , int> vertex;
  15. map<int, pair<int, int> >inv;
  16. vector<int>g[100005];
  17. int visit[100005];
  18. int ans = 0;
  19. int k = 0;
  20.  
  21. void dfs(int source){
  22.     visit[source] = 1;
  23.     int x = inv[source].first; int y = inv[source]. second;
  24.     if(cult[{x+1, y}] == 0)k++;
  25.    
  26.     if(cult[{x, y+1}] == 0)k++;
  27.        
  28.     if(cult[{x, y-1}] == 0)k++;
  29.        
  30.     if(cult[{x-1, y}] == 0)k++;
  31.    
  32.     for(int j=0; j<g[source].size(); j++){
  33.         if(visit[g[source][j]]==0){
  34.             dfs(g[source][j]);
  35.         }
  36.     }
  37. }
  38.  
  39.  
  40.  
  41. int32_t main()
  42. {
  43.     FAST_IO;
  44.     int r,c,n;
  45.     cin>>r>>c>>n;
  46.     int a,b;
  47.    
  48.     for(int i=0; i<n; i++){
  49.         visit[i] = 0;
  50.         cin>>a>>b;
  51.         cult[{a-1, b-1}] = 1;
  52.         vertex[{a-1, b-1}] = i;
  53.         inv[i] = {a-1, b-1};
  54.         v.pb({a-1, b-1});
  55.     }
  56.    
  57.     for(int i=0; i<n; i++){
  58.         int x = v[i].first;
  59.         int y = v[i].second;
  60.        
  61.         if(cult[{x+1, y}] == 1)g[vertex[{x,y}]].pb(vertex[{x+1, y}]);
  62.            
  63.         if(cult[{x, y+1}] == 1)g[vertex[{x,y}]].pb(vertex[{x, y+1}]);
  64.        
  65.         if(cult[{x, y-1}] == 1)g[vertex[{x,y}]].pb(vertex[{x, y-1}]);
  66.        
  67.         if(cult[{x-1, y}] == 1)g[vertex[{x,y}]].pb(vertex[{x-1, y}]);
  68.     }
  69.    
  70.     for(int i=0; i<n; i++){
  71.         if(visit[i]==0){
  72.             //cout<<"dfs initiated at source"<<" "<<i<<endl;
  73.             k=0;
  74.             dfs(i);
  75.         }
  76.         ans = max(k, ans);
  77.     }
  78.    
  79.     cout<<ans<<endl;
  80. }
Add Comment
Please, Sign In to add comment