fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. struct toado{
  4.     int x,y,h;
  5. };
  6. #define N 1009
  7. #define maxk 100009
  8. toado a[N*N]; int na = 0; // na là số phần tử của mảng a
  9. int h[N][N];
  10. #define ii pair <int,int>
  11. #define fi first
  12. #define se second
  13. ii P[N][N];
  14. int ds[maxk], KQ[maxk];
  15. bool cmp(toado u, toado v)
  16. {
  17.     return (u.h > v.h);
  18. }
  19. int dx[4]={-1,1,0,0};
  20. int dy[4]={0,0,-1,1};
  21.  
  22. ii Root(int x, int y)
  23. {
  24.     ii u = {x, y};
  25.     if (x == P[x][y].fi && y == P[x][y].se) return u;
  26.     P[x][y] = Root( P[x][y].fi, P[x][y].se );
  27.     return (P[x][y]);
  28. }
  29.  
  30. void Union (ii u, ii v)
  31. {
  32.     P[u.fi][u.se] = P[v.fi][v.se];
  33. }
  34.  
  35. int main()
  36. {
  37.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // thêm cái này
  38.     freopen("land.inp","r",stdin);
  39.     freopen("land.out","w",stdout);
  40.     int m, n, k;
  41.     cin >> m >> n;
  42.     for (int i=1; i<=m; i++)
  43.         for (int j=1; j<=n; j++)
  44.         {
  45.             cin >> h[i][j];
  46.             na++;
  47.             a[na] = {i,j,h[i][j]};
  48.         }
  49.  
  50.     cin >> k;
  51.     for (int i=1; i<=k; i++) cin >> ds[i];
  52.     sort(a+1, a+na+1, cmp);   //  for (int i=1; i<=na; i++) cout << a[i].h << endl;
  53.     int j = 1;
  54.     int kq = 0;
  55.     ii p0 = {0,0};
  56.     for (int i=k; i>=1; i--)
  57.     {
  58.       //  cout << "i = " << i << endl;
  59.         while (j<=na)
  60.         {
  61.             toado u = a[j];
  62.  
  63.             if (u.h <= ds[i]) break;
  64.            // cout << "   u = " << "   "<< u.x << " " << u.y << " " <<u.h<< endl;
  65.             P[u.x][u.y] = {u.x, u.y}; // Khởi tạo cho P cho u
  66.  
  67.             kq++;
  68.  
  69.             for (int t = 0; t <= 3; t++)
  70.             {
  71.                 int vx, vy;
  72.                 vx = u.x + dx[t];
  73.                 vy = u.y + dy[t];
  74.                 if (1 <= vx && vx <= m && 1 <= vy && vy <= n)
  75.                    // && P[vx][vy] == {0,0})
  76.                 {
  77.                     // nếu v chưa được thăm thì continue luôn
  78.  
  79.                     if (P[vx][vy].fi == 0 && P[vx][vy].se == 0) continue;
  80.  
  81.                     ii Pv = Root(vx, vy);
  82.                     ii Pu = Root(u.x,u.y); // Pu thay đổi nên mỗi lần kề v phải tìm lại Pu
  83.                     if (Pu != Pv)   // Nếu cha u khác cha v
  84.                     {
  85.  
  86.  
  87.                         kq--;
  88.                       //  cout << "   v = " << "   "<< vx << " " << vy << " kq =  " << kq<< endl;
  89.                       //  cout << "haha \n";
  90.                         Union(Pu, Pv);
  91.                     }
  92.                 }
  93.  
  94.             }
  95.             j++;
  96.  
  97.         }
  98.        // cout << kq << endl;
  99.         KQ[i] = kq;
  100.     }
  101.     for (int i=1; i<=k; i++)
  102.         cout << KQ[i] << " ";
  103.  
  104. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/vdMorM
language:
C++14 (clang 8.0)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!