Josif_tepe

Untitled

Jan 28th, 2026
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.82 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. const int maxn = 1e5 + 10;
  5. int idx[maxn], sz[maxn];
  6.  
  7. void init() {
  8.     for(int i = 0; i < maxn; i++) {
  9.         sz[i] = 1;
  10.         idx[i] = i;
  11.     }
  12. }
  13.  
  14. int find_root(int x) {
  15.     while(x != idx[x]) {
  16.         idx[x] = idx[idx[x]];
  17.         x = idx[x];
  18.     }
  19.     return x;
  20. }
  21. void unite(int A, int B) {
  22.     int rootA = find_root(A);
  23.     int rootB = find_root(B);
  24.    
  25.     if(rootA != rootB) {
  26.         if(sz[rootA] < sz[rootB]) {
  27.             idx[rootA] = idx[rootB];
  28.             sz[rootB] += sz[rootA];
  29.         }
  30.         else {
  31.             idx[rootB] = idx[rootA];
  32.             sz[rootA] += sz[rootB];
  33.         }
  34.     }
  35.    
  36. }
  37. bool check(int A, int B) {
  38.     return find_root(A) == find_root(B);
  39. }
  40.  
  41. struct rudnik {
  42.     int year, x, y, at, exploit;
  43.     rudnik() {}
  44.     rudnik(int _year, int _x, int _y, int _at, int _exploit) {
  45.         year = _year;
  46.         x = _x;
  47.         y = _y;
  48.         at = _at;
  49.         exploit = _exploit;
  50.     }
  51.    
  52.     bool operator < (const rudnik & tmp) const {
  53.         if(year == tmp.year) {
  54.             return exploit < tmp.exploit;
  55.         }
  56.         return year < tmp.year;
  57.     }
  58.    
  59. };
  60. int mat[305][305];
  61. int main() {
  62.     ios_base::sync_with_stdio(false);
  63.     vector<rudnik> rudnici;
  64.    
  65.     init();
  66.     int k;
  67.     cin >> k;
  68.    
  69.     vector<int> G(k);
  70.    
  71.     for(int i = 0; i < k; i++) {
  72.         cin >> G[i];
  73.         rudnici.push_back(rudnik(G[i], -1, -1, i, 1));
  74.     }
  75.     int n, m;
  76.     cin >> n >> m;
  77.    
  78.     for(int i = 0; i < n; i++) {
  79.         for(int j = 0; j < m; j++) {
  80.             cin >> mat[i][j];
  81.            
  82.             rudnici.push_back(rudnik(mat[i][j], i, j, -1, 0));
  83.         }
  84.     }
  85.    
  86.     sort(rudnici.begin(), rudnici.end());
  87.    
  88.     int oblasti = 0;
  89.     vector<int> res(k + 1);
  90.     int di[] = {-1, 1, 0, 0};
  91.     int dj[] = {0, 0, -1, 1};
  92.     vector<vector<bool>> visited(n + 1, vector<bool>(m + 1, false));
  93.     for(int i = (int) rudnici.size() - 1; i >= 0; i--) {
  94.         if(rudnici[i].exploit == 1) {
  95.             res[rudnici[i].at] = oblasti;
  96.         }
  97.         else {
  98.             int ti = rudnici[i].x, tj = rudnici[i].y;
  99.             visited[ti][tj] = true;
  100.             oblasti++;
  101.            
  102.             for(int k = 0; k < 4; k++) {
  103.                 int pi = ti + di[k], pj = tj + dj[k];
  104.                 if(pi >= 0 and pi < n and pj >= 0 and pj < m and visited[pi][pj]) {
  105.                     int A = pi * m + pj;
  106.                     int B = ti * m + tj;
  107.                    
  108.                     if(!check(A, B)) {
  109.                         oblasti--;
  110.                     }
  111.                     unite(A, B);
  112.                 }
  113.             }
  114.         }
  115.     }
  116.    
  117.     for(int i = 0; i < k; i++) {
  118.         cout << res[i] << endl;
  119.     }
  120.    
  121.    
  122.     return 0;
  123. }
  124.  
Advertisement
Add Comment
Please, Sign In to add comment