ash_sinha

Untitled

Oct 18th, 2022
671
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.61 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. using namespace __gnu_pbds;
  4. using namespace std;
  5.  
  6. #define ff              first
  7. #define ss              second
  8. #define int             long long
  9. #define pb              push_back
  10. #define mp              make_pair
  11. #define pii             pair<int,int>
  12. #define vi              vector<int>
  13. #define mii             map<int,int>
  14. #define pqb             priority_queue<int>
  15. #define pqs             priority_queue<int,vi,greater<int> >
  16. #define setbits(x)      __builtin_popcountll(x)
  17. #define zrobits(x)      __builtin_ctzll(x)
  18. #define mod             1000000007
  19. #define inf             1e18
  20. #define ps(x,y)         fixed<<setprecision(y)<<x
  21. #define mk(arr,n,type)  type *arr=new type[n];
  22. #define w(x)            int x; cin>>x; while(x--)
  23. mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());
  24. #define fastio          ios_base::sync_with_stdio(0); cin.tie(0);
  25.  
  26. int dsu(int x,vector<int> &p)
  27. {
  28.     while(x!=p[x])
  29.     {
  30.         p[x]=p[p[x]];
  31.         x=p[x];
  32.     }
  33.     return p[x];
  34. }
  35. void merge(int a,int b,vector<int> &p,vector<int> &sz)
  36. {
  37.     a=dsu(a,p);b=dsu(b,p);
  38.     if(a==b) return ;
  39.     if(sz[b]>sz[a]) swap(a,b);
  40.     sz[a]+=sz[b];
  41.     p[b]=p[a];
  42. }
  43. void up(int x1,int y1,int x2,int y2,map<pair<int,int>,int> &hash,vector<int> &p,vector<int>&sz,vector<vector<int>> &grid)
  44. {
  45.     if(hash.find({x1,y1})==hash.end() || hash.find({x2,y2})==hash.end()) return;
  46.     if(grid[x1][y1]==grid[x2][y2] && grid[x1][y1]==1)
  47.     merge(hash[{x1,y1}],hash[{x2,y2}],p,sz);
  48. }
  49.  
  50. vector<int> onesGroups(vector<vector<int>> &grid,vector<int> &q)
  51. {
  52.     int n=grid.size(),m=grid[0].size(),cnt=0;
  53.     map<pair<int,int>,int> hash;
  54.     for(int i=0;i<n;i++)
  55.     {
  56.         for(int j=0;j<m;j++) {hash[{i,j}]=cnt;cnt++;}
  57.     }
  58.     vector<int> p(cnt),sz(cnt,1),h(n*m,0);
  59.     for(int i=0;i<cnt;i++) p[i]=i;
  60.     for(int i=0;i<n;i++){
  61.         for(int j=0;j<m;j++){
  62.             up(i,j,i,j-1,hash,p,sz,grid);
  63.             up(i,j,i,j+1,hash,p,sz,grid);
  64.             up(i,j,i-1,j,hash,p,sz,grid);
  65.             up(i,j,i+1,j,hash,p,sz,grid);
  66.  
  67.         }
  68.     }
  69.     for(int i=0;i<n;i++)
  70.     {
  71.         for(int j=0;j<m;j++)
  72.         {
  73.             int x=hash[{i,j}];
  74.             if(grid[i][j]==1 && p[x]==x) h[sz[x]]++;
  75.         }
  76.     }
  77.     for(int i=0;i<q.size();i++) q[i]=h[q[i]];
  78.     return q;
  79.  
  80. }
  81.  
  82.  
  83.  
  84. int32_t main()
  85. {
  86.     int n,m;
  87.     cin>>n>>m;
  88.     vi q={6,1,8,2};
  89.     vector<vi> grid(n,vi(m,0));
  90.     for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>grid[i][j];
  91.     q=onesGroups(grid,q);
  92.     for(auto x:q) cout<<x<<" ";
  93.    
  94. return 0;
  95. }
Advertisement
Add Comment
Please, Sign In to add comment