Guest User

DSU_B

a guest
Oct 11th, 2025
48
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.28 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int dx[4] = {-1, 0, 0, 1};
  5. int dy[4] = {0, -1, 1, 0};
  6. int res = 0;
  7. pair <int, int> ffind(pair <int, int> x){
  8.  
  9.     while (dsu[x.f][x.s] != x){
  10.         x = dsu[x.f][x.s];
  11.     }
  12.  
  13.     return x;
  14. }
  15.  
  16. void uunion(pair <int, int> x, pair <int, int> y){
  17.     x = ffind(x);
  18.     y = ffind(y);
  19.  
  20.     if (h[x.f][x.s] > h[y.f][y.s]){
  21.         dsu[y.f][y.s] = x;
  22.         cnt[x.f][x.s] += cnt[y.f][y.s];
  23.     }
  24.     else{
  25.         dsu[x.f][x.s] = y;
  26.         cnt[y.f][y.s] += cnt[x.f][x.s];
  27.         if (h[x.f][x.s] == h[y.f][y.s]){
  28.             h[y.f][y.s]++;
  29.         }
  30.     }
  31. }
  32.  
  33. void dfs(int x, int y, int val){
  34.     if (res == 0){
  35.         return;
  36.     }
  37.     used[x][y] = val;
  38.     res--;
  39.     for (int i = 0; i < 4; i++){
  40.         int tox = x + dx[i];
  41.         int toy = y + dy[i];
  42.         if (check(tox, toy) && !used[tox][toy]
  43.             && a[tox][toy] >= val && res > 0){
  44.             dfs(tox, toy, val);
  45.         }
  46.     }
  47.  
  48. }
  49.  
  50. int main(){
  51.     int n;
  52.     cin >> n >> m >> k;
  53.     vector <pair <int, pair <int, int> > > vec;
  54.     for (int i = 1; i <= n; i++){
  55.         for (int j = 1; j <= m; j++){
  56.             cin >> a[i][j];
  57.             dsu[i][j] = {i, j};
  58.             h[i][j] = 1;
  59.             cnt[i][j] = 1;
  60.             was[i][j] = 0;
  61.             vec.pb({a[i][j], {i, j}});
  62.         }
  63.     }
  64.  
  65.     sort(vec.begin(), vec.end());
  66.     reverse(vec.begin(), vec.end());
  67.  
  68.     for (int i = 0; i < vec.size(); i++){
  69.         int val = vec[i].f;
  70.         int x = vec[i].s.f;
  71.         int y = vec[i].s.s;
  72.  
  73.         was[x][y] = 1;
  74.         for (int j = 0; j < 4; j++){
  75.             int tox = x + dx[j];
  76.             int toy = y + dy[j];
  77.             if (check(tox, toy) && was[tox][toy]){
  78.                 uunion(make_pair(x, y), make_pair(tox, toy));
  79.             }
  80.         }
  81.  
  82.         if (k % val == 0){
  83.             pair <int, int> z = ffind(make_pair(x, y));
  84.             if (cnt[z.f][z.s] * val >= k){
  85.                 ansx = x;
  86.                 ansy = y;
  87.                 break;
  88.             }
  89.         }
  90.     }
  91.     res = k / a[ansx][ansy];
  92.     dfs(ansx, ansy, a[ansx][ansy]);
  93.  
  94.     for (int i = 1; i <= n; i++){
  95.         for (int j = 1; j <= m; j++){
  96.             cout << used[i][j] << ' ';
  97.         }
  98.         cout << "\n";
  99.     }
  100.  
  101.  
  102.     return 0;
  103. }
  104.  
  105.  
Advertisement
Add Comment
Please, Sign In to add comment