Advertisement
Guest User

collapse

a guest
Jul 8th, 2018
441
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.13 KB | None | 0 0
  1. #include "collapse.h"
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. const int N = 100005;
  8.  
  9. struct Event {
  10.     int T, type, x, y;
  11.  
  12.     bool operator < (const Event& rhs) const {
  13.         return (T == rhs.T) ? type < rhs.type : T < rhs.T;
  14.     }
  15. };
  16.  
  17. struct Edge {
  18.     int id, u, v;
  19.  
  20.     bool operator < (const Edge& rhs) const {
  21.         return u < rhs.u;
  22.     }
  23. };
  24.  
  25. int n;
  26. int par[N];
  27. int res[N];
  28. int f[2][N];
  29. int pos[N];
  30. bool state[N];
  31. bool iedge[N];
  32. bool inode[N];
  33. vector<Event> vec, buf;
  34. vector< pair<int, int> > dsu[2][500];
  35. map< pair<int, int>, int > label;
  36. vector<Edge> E1, E2;
  37.  
  38. int find(int u) { return u == par[u] ? u : par[u] = find(par[u]); }
  39.  
  40. bool join(int u, int v) {
  41.     u = find(u), v = find(v);
  42.     if (inode[u]) swap(u, v); // root prefer important node
  43.     par[u] = v; return u != v;
  44. }
  45.  
  46. void solve() {
  47.     vector<int> vnode;
  48.     vector<Edge> vedge;
  49.  
  50.     int cnt = 0;
  51.     for (auto i : buf) {
  52.         if (i.type < 0) {
  53.             int id = label[{i.x, i.y}];
  54.             if (!iedge[id]) {
  55.                 iedge[id] = 1;
  56.                 vedge.push_back({id, i.x, i.y});
  57.             }
  58.             if (!inode[i.x]) {
  59.                 inode[i.x] = 1, vnode.push_back(i.x);
  60.             }
  61.             if (!inode[i.y]) {
  62.                 inode[i.y] = 1, vnode.push_back(i.y);
  63.             }
  64.         }
  65.         else pos[i.type] = cnt++;
  66.     }
  67.  
  68.     {  
  69.         vector< pair<int, int> > vec1;
  70.         for (auto i : buf) {
  71.             if (i.type >= 0) vec1.push_back({i.x, i.type});
  72.         }
  73.         sort(vec1.begin(), vec1.end());
  74.         for (int i = 0; i < n; ++i) par[i] = i;
  75.         int ptr = 0, cur = 0, cnt = 0;
  76.         for (auto i : vec1) {
  77.             while (cur < i.first) ++cur, ++cnt;
  78.             while (ptr < E1.size() && E1[ptr].u <= i.first) {
  79.                 if (!iedge[E1[ptr].id] && state[E1[ptr].id]) {
  80.                     cnt -= join(E1[ptr].u, E1[ptr].v);
  81.                 }
  82.                 ++ptr;
  83.             }
  84.             f[0][i.second] = cnt;
  85.             for (auto j : vnode) {
  86.                 dsu[0][pos[i.second]].push_back({j, find(j)});
  87.             }
  88.         }
  89.     }
  90.  
  91.     {  
  92.         vector< pair<int, int> > vec2;
  93.         for (auto i : buf) {
  94.             if (i.type >= 0) vec2.push_back({i.x + 1, i.type});
  95.         }
  96.         sort(vec2.begin(), vec2.end());
  97.         reverse(vec2.begin(), vec2.end());
  98.         for (int i = 0; i < n; ++i) par[i] = i;
  99.         int ptr = 0, cur = 0, cnt = 0;
  100.         for (auto i : vec2) {
  101.             while (cur < n - i.first + 1) ++cur, ++cnt;
  102.             while (ptr < E2.size() && E2[ptr].u >= i.first) {
  103.                 if (!iedge[E2[ptr].id] && state[E2[ptr].id]) {
  104.                     cnt -= join(E2[ptr].u, E2[ptr].v);
  105.                 }
  106.                 ++ptr;
  107.             }
  108.             f[1][i.second] = cnt;
  109.             for (auto j : vnode) {
  110.                 dsu[1][pos[i.second]].push_back({j, find(j)});
  111.             }
  112.         }
  113.     }
  114.  
  115.     for (auto i : buf) {
  116.         if (i.type < 0) {
  117.             int id = label[{i.x, i.y}];
  118.             state[id] ^= 1; continue;
  119.         }
  120.         int id = i.type;
  121.         for (int j = 0; j < 2; ++j) {
  122.             for (auto k : dsu[j][pos[id]]) par[k.first] = k.second;
  123.             for (auto k : vnode) {
  124.                 if (j == 0 && k > i.x || j == 1 && k <= i.x) continue;
  125.                 f[j][id] -= par[k] == k;
  126.             }
  127.             for (auto k : vedge) {
  128.                 // k.u < k.v
  129.                 if (state[k.id] && (k.v <= i.x || k.u > i.x)) join(k.u, k.v);
  130.             }
  131.             for (auto k : vnode) {
  132.                 if (j == 0 && k > i.x || j == 1 && k <= i.x) continue;
  133.                 f[j][id] += par[k] == k;
  134.             }
  135.         }
  136.         res[id] = f[0][id] + f[1][id];
  137.     }
  138.  
  139.     for (int i = 0; i < cnt; ++i) dsu[0][i].clear(), dsu[1][i].clear();
  140.     for (auto i : buf) {
  141.         if (i.type < 0) {
  142.             iedge[label[{i.x, i.y}]] = inode[i.x] = inode[i.y] = 0;
  143.         }
  144.     }
  145.     buf.clear();
  146. }
  147.  
  148. vector<int> simulateCollapse(
  149.     int _n,
  150.     vector<int> T,
  151.     vector<int> X,
  152.     vector<int> Y,
  153.     vector<int> W,
  154.     vector<int> P
  155. ) {
  156.     n = _n;
  157.     int c = T.size();
  158.     int q = W.size();
  159.  
  160.     for (int i = 0; i < c; ++i) {
  161.         if (X[i] > Y[i]) swap(X[i], Y[i]);
  162.         vec.push_back({i, -(T[i] + 1), X[i], Y[i]});
  163.     }
  164.     for (int i = 0; i < q; ++i) {
  165.         vec.push_back({W[i], i, P[i], 0});
  166.     }
  167.     sort(vec.begin(), vec.end());
  168.  
  169.     int cnt = 0;
  170.     for (int i = 0; i < c; ++i) {
  171.         if (label[{X[i], Y[i]}]) continue;
  172.         label[{X[i], Y[i]}] = ++cnt;
  173.         E1.push_back({cnt, Y[i], X[i]});
  174.         E2.push_back({cnt, X[i], Y[i]});
  175.     }
  176.  
  177.     sort(E1.begin(), E1.end());
  178.     sort(E2.begin(), E2.end());
  179.     reverse(E2.begin(), E2.end());
  180.  
  181.     for (int i = 0; i < vec.size(); ++i) {
  182.         buf.push_back(vec[i]);
  183.         if (buf.size() == 365) solve();
  184.     }
  185.     if (buf.size()) solve();
  186.  
  187.     vector<int> vres;
  188.     for (int i = 0; i < q; ++i) vres.push_back(res[i]);
  189.     return vres;
  190. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement