ash_sinha

Untitled

Oct 18th, 2022
859
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.58 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. void dfs(int i,int j,vector<vi> &vis,vector<vi>&grid,int &cnt)
  51. {
  52.     if(i<0 || i>=grid.size() || j<0 || j>=grid[0].size() || vis[i][j]==1 || grid[i][j]==0) return;
  53.     vis[i][j]=1;
  54.     cnt++;
  55.     dfs(i+1,j,vis,grid,cnt);
  56.     dfs(i-1,j,vis,grid,cnt);
  57.     dfs(i,j+1,vis,grid,cnt);
  58.     dfs(i,j-1,vis,grid,cnt);
  59. }
  60.  
  61. vector<int> onesGroups(vector<vector<int>> &grid,vector<int> &q)
  62. {
  63.     int n=grid.size(),m=grid[0].size(),cnt=0;
  64.     vector<vi> vis(n,vi(m,0));
  65.     vi h(n*m+1,0);
  66.     for(int i=0;i<n;i++){
  67.         for(int j=0;j<m;j++){
  68.             int cnt=0;
  69.             if(grid[i][j]==1 && vis[i][j]==0){
  70.                 dfs(i,j,vis,grid,cnt);
  71.                 h[cnt]++;
  72.             }
  73.         }
  74.     }
  75.     for(int i=0;i<q.size();i++) q[i]=h[q[i]];
  76.     return q;
  77.  
  78. }
  79.  
  80.  
  81.  
  82.  
  83.  
  84.  
  85. int32_t main()
  86. {
  87.     int n,m;
  88.     cin>>n>>m;
  89.     vi q={6,1,8,2};
  90.     vector<vi> grid(n,vi(m,0));
  91.     for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>grid[i][j];
  92.     q=onesGroups(grid,q);
  93.     for(auto x:q) cout<<x<<" ";
  94.    
  95. return 0;
  96. }
Advertisement
Add Comment
Please, Sign In to add comment