Josif_tepe

Untitled

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