Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- using namespace __gnu_pbds;
- using namespace std;
- #define ff first
- #define ss second
- #define int long long
- #define pb push_back
- #define mp make_pair
- #define pii pair<int,int>
- #define vi vector<int>
- #define mii map<int,int>
- #define pqb priority_queue<int>
- #define pqs priority_queue<int,vi,greater<int> >
- #define setbits(x) __builtin_popcountll(x)
- #define zrobits(x) __builtin_ctzll(x)
- #define mod 1000000007
- #define inf 1e18
- #define ps(x,y) fixed<<setprecision(y)<<x
- #define mk(arr,n,type) type *arr=new type[n];
- #define w(x) int x; cin>>x; while(x--)
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- #define fastio ios_base::sync_with_stdio(0); cin.tie(0);
- int dsu(int x,vector<int> &p)
- {
- while(x!=p[x])
- {
- p[x]=p[p[x]];
- x=p[x];
- }
- return p[x];
- }
- void merge(int a,int b,vector<int> &p,vector<int> &sz)
- {
- a=dsu(a,p);b=dsu(b,p);
- if(a==b) return ;
- if(sz[b]>sz[a]) swap(a,b);
- sz[a]+=sz[b];
- p[b]=p[a];
- }
- 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)
- {
- if(hash.find({x1,y1})==hash.end() || hash.find({x2,y2})==hash.end()) return;
- if(grid[x1][y1]==grid[x2][y2] && grid[x1][y1]==1)
- merge(hash[{x1,y1}],hash[{x2,y2}],p,sz);
- }
- vector<int> onesGroups(vector<vector<int>> &grid,vector<int> &q)
- {
- int n=grid.size(),m=grid[0].size(),cnt=0;
- map<pair<int,int>,int> hash;
- for(int i=0;i<n;i++)
- {
- for(int j=0;j<m;j++) {hash[{i,j}]=cnt;cnt++;}
- }
- vector<int> p(cnt),sz(cnt,1),h(n*m,0);
- for(int i=0;i<cnt;i++) p[i]=i;
- for(int i=0;i<n;i++){
- for(int j=0;j<m;j++){
- up(i,j,i,j-1,hash,p,sz,grid);
- up(i,j,i,j+1,hash,p,sz,grid);
- up(i,j,i-1,j,hash,p,sz,grid);
- up(i,j,i+1,j,hash,p,sz,grid);
- }
- }
- for(int i=0;i<n;i++)
- {
- for(int j=0;j<m;j++)
- {
- int x=hash[{i,j}];
- if(grid[i][j]==1 && p[x]==x) h[sz[x]]++;
- }
- }
- for(int i=0;i<q.size();i++) q[i]=h[q[i]];
- return q;
- }
- int32_t main()
- {
- int n,m;
- cin>>n>>m;
- vi q={6,1,8,2};
- vector<vi> grid(n,vi(m,0));
- for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>grid[i][j];
- q=onesGroups(grid,q);
- for(auto x:q) cout<<x<<" ";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment