FuFsQ

c_cmp.cpp

Nov 22nd, 2020
525
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdc++.h>
  2. #include <iomanip>
  3.  
  4. using namespace std;
  5.  
  6. static int curr_point;
  7. static map<int, pair<int, int> > anc_pts;
  8. static vector<int> assoc_tbl;
  9.  
  10. void rewrite_assoc(int g_old, int g_new) {
  11.     for (int i = 1; i < assoc_tbl.size(); ++i) {
  12.         if (assoc_tbl[i] == g_old) {
  13.             assoc_tbl[i] = g_new;
  14.         }
  15.     }
  16.     assoc_tbl[g_old] = g_new;
  17. }
  18.  
  19. int create_new_id() {
  20.     ++curr_point;
  21.     assoc_tbl.push_back(curr_point);
  22.     return curr_point;
  23. }
  24.  
  25. void create_first_anchor(int id, int x, int y) {
  26.     anc_pts[id] = pair<int, int>(x, y);
  27. }
  28.  
  29. int get_id(int x, int y, const vector<vector<int> >& map) {
  30.     return assoc_tbl[abs(map[x][y])];
  31. }
  32.  
  33. void fix_new_anchor(int x, int y, int raw_id, vector<vector<int> >& map) {
  34.     int resolved_id = raw_id;
  35.     pair<int, int> old_anc = anc_pts[resolved_id];
  36.     // map[old_anc.first][old_anc.second] = resolved_id;
  37.     anc_pts[resolved_id] = pair<int, int>(x, y);
  38. }
  39.  
  40. void s_union(int x, int y, vector<vector<int> >& mp, const vector<pair<int, int> >& dsp) {
  41.     int fx, fy;
  42.     int filler = get_id(x, y, mp);
  43.  
  44.     if (filler == 0) {
  45.         filler = create_new_id();
  46.         create_first_anchor(filler, x, y);
  47.  
  48.         for (int j = 0; j < dsp.size(); ++j) {
  49.             fx = x + dsp[j].first;
  50.             fy = y + dsp[j].second;
  51.  
  52.             if ((mp[fx][fy] <= filler) && (mp[fx][fy] >= 0)) // do not overwrite points
  53.                 mp[fx][fy] = filler;
  54.         }
  55.         mp[x][y] = -filler;
  56.     } else {
  57.         fix_new_anchor(x, y, filler, mp);
  58.         set<int> ids_list;
  59.         int cid;
  60.         for (int j = 0; j < dsp.size(); ++j) {
  61.             fx = x + dsp[j].first;
  62.             fy = y + dsp[j].second;
  63.  
  64.             if (mp[fx][fy] < 0) { // Ðÿäîì åñòü âåðøèíà, íóæíî îáúåäèíÿòü îáëàñòè
  65.                 ids_list.insert(abs(mp[fx][fy]));
  66.             }
  67.  
  68.             if ((mp[fx][fy] <= filler) && (mp[fx][fy] >= 0)) {
  69.                 mp[fx][fy] = filler;
  70.             }
  71.         }
  72.         /*
  73.         cout << "GET ids_list: \n";
  74.         for (auto sE : ids_list) {
  75.             cout << sE << ' ';
  76.         }
  77.         */
  78.  
  79.         mp[x][y] = -filler;
  80.  
  81.         if (ids_list.size() > 0) {
  82.             int area_max = -555;
  83.             vector<int> regions;
  84.             for (set<int>::iterator it = ids_list.begin(); it != ids_list.end(); ++it) {
  85.                 if (abs(*it) > area_max) {
  86.                     area_max = abs(*it);
  87.                     regions.push_back(assoc_tbl[abs(*it)]);
  88.                 }
  89.             }
  90.             int new_id_ = assoc_tbl[area_max];
  91.             if (area_max > filler) {
  92.                 //
  93.                 for (int i = 0; i < regions.size(); ++i) {
  94.                     rewrite_assoc(regions[i], new_id_);
  95.                 }
  96.             }
  97.             else {
  98.                 for (int i = 0; i < regions.size(); ++i) {
  99.                     rewrite_assoc(regions[i], filler);
  100.                 }
  101.             }
  102.         }
  103.     }
  104.  
  105. }
  106.  
  107. int main(int argc, char** argv) {
  108.     curr_point = 1;
  109.     assoc_tbl = vector<int>(2);
  110.     int n, m, k;
  111.     scanf_s("%d %d %d", &n, &m, &k);
  112.  
  113.     vector<vector<int> > mapp(n + 2, vector<int>(m + 2, 0));
  114.     vector<pair<int, int> > dsp(8);
  115.  
  116.     dsp[0] = pair<int, int>(-1, -1);
  117.     dsp[1] = pair<int, int>(0, -1);
  118.     dsp[2] = pair<int, int>(1, -1);
  119.     dsp[3] = pair<int, int>(-1, 0);
  120.     dsp[4] = pair<int, int>(1, 0);
  121.     dsp[5] = pair<int, int>(-1, 1);
  122.     dsp[6] = pair<int, int>(0, 1);
  123.     dsp[7] = pair<int, int>(1, 1);
  124.  
  125.     int x, y;
  126.  
  127.     for (int i = 0; i < k; ++i) {
  128.         scanf_s("%d %d", &x, &y);
  129.         s_union(x, y, mapp, dsp);
  130.  
  131.         /*
  132.         for (int t = 0; t < mapp.size(); ++t) {
  133.             for (int j = 0; j < mapp[t].size(); ++j) {
  134.                 cout << setw(3);
  135.                 cout << mapp[t][j] << " ";
  136.             }
  137.             cout << "\n";
  138.         }
  139.  
  140.         for (int t = 1; t < assoc_tbl.size(); ++t) {
  141.             cout << t << " -> " << assoc_tbl[t] << "\n";
  142.         }
  143.         */
  144.     }
  145.  
  146.     int cansw = 0;
  147.     for (int it = 2; it < assoc_tbl.size(); ++it) {
  148.         if (it == assoc_tbl[it]) {
  149.             ++cansw;
  150.         }
  151.     }
  152.  
  153.     cout << cansw;
  154.  
  155.     return 0;
  156. }
RAW Paste Data