Josif_tepe

Untitled

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