mickypinata

FORCE-T1012B: Chemical Table

Jul 4th, 2021 (edited)
1,108
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef pair<int, int> pii;
  5. typedef tuple<int, int, int> tiii;
  6.  
  7. const int N = 2e5;
  8.  
  9. bool foundRow[N + 1], foundCol[N + 1];
  10. int ds[N + 1], sz[N + 1];
  11. vector<pii> colrowPairs;
  12. vector<tiii> edges;
  13.  
  14. int dsFind(int u){
  15.     if(ds[u] == u){
  16.         return u;
  17.     }
  18.     return ds[u] = dsFind(ds[u]);
  19. }
  20.  
  21. int main(){
  22.  
  23.     int row, col, nChem;
  24.     scanf("%d%d%d", &row, &col, &nChem);
  25.     if(nChem == 0){
  26.         cout << row + col - 1;
  27.         return 0;
  28.     }
  29.     for(int i = 1; i <= row; ++i){
  30.         ds[i] = i;
  31.         sz[i] = 1;
  32.     }
  33.     int r, c;
  34.     for(int i = 1; i <= nChem; ++i){
  35.         scanf("%d%d", &r, &c);
  36.         foundCol[c] = true;
  37.         foundRow[r] = true;
  38.         colrowPairs.emplace_back(c, r);
  39.     }
  40.     int sum = 0;
  41.     for(int i = 1; i <= row; ++i){
  42.         if(!foundRow[i]){
  43.             ++sum;
  44.             colrowPairs.emplace_back(c, i);
  45.         }
  46.     }
  47.     for(int i = 1; i <= col; ++i){
  48.         if(!foundCol[i]){
  49.             ++sum;
  50.             colrowPairs.emplace_back(i, r);
  51.         }
  52.     }
  53.  
  54.     sort(colrowPairs.begin(), colrowPairs.end());
  55.     for(int i = 0; i < (int)colrowPairs.size() - 1; ++i){
  56.         int w = colrowPairs[i + 1].first - colrowPairs[i].first;
  57.         int u = colrowPairs[i].second;
  58.         int v = colrowPairs[i + 1].second;
  59.         edges.emplace_back(w, u, v);
  60.     }
  61.     sort(edges.begin(), edges.end());
  62.  
  63.     for(tiii t : edges){
  64.         int w = get<0>(t);
  65.         int u = get<1>(t);
  66.         int v = get<2>(t);
  67.         u = dsFind(u);
  68.         v = dsFind(v);
  69.         if(u != v){
  70.             if(sz[u] < sz[v]){
  71.                 swap(u, v);
  72.             }
  73.             ds[v] = u;
  74.             sz[u] += sz[v];
  75.             sum += w;
  76.         }
  77.     }
  78.     cout << sum;
  79.  
  80.     return 0;
  81. }
  82.  
  83. // AQUABLITZ'S SOLUTION
  84. #include <bits/stdc++.h>
  85. using namespace std;
  86.  
  87. const int N = 2e5;
  88. const int M = 2e5;
  89.  
  90. int ds[N + M + 1], sz[N + M + 1];
  91.  
  92. int dsFind(int u){
  93.     if(ds[u] == u){
  94.         return u;
  95.     }
  96.     return ds[u] = dsFind(ds[u]);
  97. }
  98.  
  99. int main(){
  100.  
  101.     int row, col, nChem;
  102.     scanf("%d%d%d", &row, &col, &nChem);
  103.     for(int i = 1; i <= row + col; ++i){
  104.         ds[i] = i;
  105.         sz[i] = 1;
  106.     }
  107.     int compCnt = row + col;
  108.     for(int i = 1; i <= nChem; ++i){
  109.         int u, v;
  110.         scanf("%d%d", &u, &v);
  111.         v += row;
  112.         u = dsFind(u);
  113.         v = dsFind(v);
  114.         if(u != v){
  115.             if(sz[u] < sz[v]){
  116.                 swap(u, v);
  117.             }
  118.             ds[v] = u;
  119.             sz[u] += sz[v];
  120.             --compCnt;
  121.         }
  122.     }
  123.     cout << compCnt - 1;
  124.  
  125.     return 0;
  126. }
  127.  
RAW Paste Data Copied