MinhNGUYEN2k4

Untitled

Sep 20th, 2021
558
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define ii pair<int,int>
  3. #define iii pair<int,ii>
  4. #define fi first
  5. #define se second
  6.  
  7. using namespace std;
  8.  
  9. int n, m, a[1005][1005];
  10. int t;
  11. int q[100005];
  12. vector<iii> node;
  13. bool vst[1005][1005];
  14. int dx[4] = {1,-1,0,0};
  15. int dy[4] = {0,0,1,-1};
  16. int par[1005*1005];
  17. int cnt;
  18. int kq[100005];
  19.  
  20. int get(int u){
  21.     return (u==par[u] ? u : par[u]=get(par[u]));
  22. }
  23.  
  24. void join(int u, int v){
  25.     u = get(u);
  26.     v = get(v);
  27.     if (u==v) return;
  28.     par[v] = u;
  29.     cnt--;
  30. }
  31.  
  32. bool ok(int u, int v){
  33.     if (1 <= u && u <= n && 1 <= v && v <= m) return true;
  34.     return false;
  35. }
  36.  
  37. int main()
  38. {
  39.     if (fopen("test.inp","r")) freopen("test.inp","r",stdin);
  40.     ios_base::sync_with_stdio(false);
  41.     cin.tie(0); cout.tie(0);
  42.     cin >> n >> m;
  43.     for(int i=1; i<=n; i++){
  44.         for(int j=1; j<=m; j++){
  45.             cin >> a[i][j];
  46.             node.push_back(iii(a[i][j],ii(i,j)));
  47.         }
  48.     }
  49.     cin >> t;
  50.     for(int i=1; i<=t; i++) cin >> q[i];
  51.     for(int i=1; i<=n*m; i++) par[i] = i;
  52.     sort(node.begin(),node.end(),greater<iii>());
  53.     int j=0;
  54.     for(int i=t; i>=1; i--){
  55.         while (j<(int)node.size() && node[j].fi > q[i]){
  56.             int u = node[j].se.fi;
  57.             int v = node[j].se.se;
  58.             vst[u][v] = true;
  59.             ++cnt;
  60.             for(int k=0; k<4; k++){
  61.                 int x = u + dx[k];
  62.                 int y = v + dy[k];
  63.                 if (ok(x,y) && vst[x][y]) join((u-1)*m+v,(x-1)*m+y);
  64.             }
  65.             j++;
  66.         }
  67.         kq[i] = cnt;
  68.     }
  69.     for(int i=1; i<=t; i++) cout << kq[i] << ' ';
  70.     return 0;
  71. }
  72.  
RAW Paste Data