Advertisement
Guest User

APIO B....

a guest
May 28th, 2019
618
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.71 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. //#pragma GCC optimize("Ofast")
  3.  
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7.  
  8. #ifdef ONPC
  9. mt19937 rnd(228);
  10. #else
  11. mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
  12. #endif
  13.  
  14. const int BLOCK = 750;
  15.  
  16. const int N = 1e5 + 7;
  17.  
  18. int dsu[N];
  19. int sz[N];
  20. bool bad[N];
  21. int w[N];
  22. int u[N], v[N];
  23.  
  24. inline int get(int v)
  25. {
  26.     if (dsu[v] == v) return v;
  27.     return dsu[v] = get(dsu[v]);
  28. }
  29.  
  30. inline void uni(int u, int v)
  31. {
  32.     u = get(u), v = get(v);
  33.     if (u == v) return;
  34.     if (sz[u] > sz[v]) swap(u, v);
  35.     dsu[u] = v;
  36.     sz[v] += sz[u];
  37. }
  38.  
  39. int gays[N];
  40. int spanning[N];
  41. int was_id[N];
  42. int par[N];
  43. bool vis[N];
  44. int ans[N];
  45. vector <int> events[N];
  46. vector <pair <int, int> > gr[N];
  47. bool flex[N];
  48.  
  49. int marked[N];
  50. int ind[N];
  51.  
  52. bool cmp(int i, int j) {
  53.     if (w[i] == w[j]) return i < j;
  54.     else return w[i] < w[j];
  55. }
  56.  
  57. int edge_sz = 0;
  58.  
  59. int nxt[N];
  60. int fst[N];
  61. int id[N];
  62. int us[N];
  63.  
  64. int tt = 0;
  65.  
  66. void add(int a, int b) {
  67.     nxt[edge_sz] = fst[a];
  68.     fst[a] = edge_sz;
  69.     id[edge_sz] = b;
  70.     edge_sz++;
  71. }
  72.  
  73. int dfs(int v) {
  74.     if (us[v] == tt) {
  75.         return 0;
  76.     }
  77.     us[v] = tt;
  78.     int sum = sz[v];
  79.     for (int x = fst[v]; x; x = nxt[x]) {
  80.         sum += dfs(id[x]);
  81.     }
  82.     return sum;
  83. }
  84.  
  85. int _a[N], _b[N];
  86.  
  87. int main()
  88. {
  89. #ifdef ONPC
  90.     freopen("a.in", "r", stdin);
  91. #endif
  92.     ios::sync_with_stdio(0);
  93.     cin.tie(0);
  94.     int n = 50000, m = 49999;
  95.     int inf = 1e9;
  96.     cin >> n >> m;
  97.     for (int i = 0; i < m; i++)
  98.     {
  99.         u[i] = rnd() % n, v[i] = rnd() % n;
  100.         w[i] = rnd() % inf;
  101.         cin >> u[i] >> v[i] >> w[i];
  102.         u[i]--, v[i]--;
  103.         ind[i] = i;
  104.         w[i] *= -1;
  105.     }
  106.     int q = 100000;
  107.     cin >> q;
  108.     vector <int> t(q), a(q), b(q);
  109.     for (int i = 0; i < q; i++)
  110.     {
  111.         cin >> t[i] >> a[i] >> b[i];
  112.         a[i]--;
  113.         //  t[i] = rnd() % 2 + 1;
  114.         //t[i] = rnd() % 2 + 1;
  115.         //a[i] = rnd() % n;
  116.         //b[i] = rnd() % inf;
  117.         //a[i]--;
  118.         b[i] *= -1;
  119.         if (t[i] == 2) events[i].reserve(BLOCK);
  120.     }
  121.  
  122.     for (int i = 0; i < n; i++)
  123.     {
  124.         dsu[i] = i;
  125.         sz[i] = 1;
  126.     }
  127.     set <pair <int,int> > glob;
  128.     for (int i = 0; i < m; i++)
  129.     {
  130.         glob.insert({w[i], i});
  131.     }
  132.     int x = 0;
  133.     for (auto &c : glob) {
  134.         ind[x++] = c.second;
  135.     }
  136.     vector <pair <int, int> > e;
  137.     int sum = 0;
  138.     for (int i = 0; i < q; i += BLOCK)
  139.     {
  140.         for (int i = 0; i < m; i++) bad[i] = 0, flex[i] = 0;
  141.         int l = i, r = min(q, i + BLOCK);
  142.         for (int ptr = l; ptr < r; ptr++)
  143.         {
  144.             if (t[ptr] == 1)
  145.             {
  146.                 bad[a[ptr]] = 1;
  147.             }
  148.         }
  149.         for (int i = 0; i < n; i++) dsu[i] = i, sz[i] = 1;
  150.         for (int i = 0; i < m; i++)
  151.         {
  152.             int id = ind[i];
  153.             if (!bad[id] && get(u[id]) != get(v[id]))
  154.             {
  155.                 uni(u[id], v[id]);
  156.                 flex[id] = true;
  157.             }
  158.         }
  159.         for (int i = 0; i < n; i++) dsu[i] = i,sz[i] = 1;
  160.         int span_len = 0;
  161.         for (int i = 0; i < m; i++)
  162.         {
  163.             int id = ind[i];
  164.             if (get(u[id]) != get(v[id]))
  165.             {
  166.                 uni(u[id], v[id]);
  167.                 flex[id] = false;
  168.                 if (!bad[id])
  169.                 {
  170.                     spanning[span_len++] = id;
  171.                 }
  172.             }
  173.         }
  174.         for (int i = 0; i < n; i++) dsu[i] = i, sz[i] = 1;
  175.         sum = 0;
  176.         for (int i = 0; i < m; i++)
  177.         {
  178.             if (bad[i] || flex[i])
  179.             {
  180.                 marked[sum++] = i;
  181.             }
  182.         }
  183.         e.clear();
  184.         for (int ptr = l; ptr < r; ptr++)
  185.         {
  186.             if (t[ptr] == 1)
  187.             {
  188.                 w[a[ptr]] = b[ptr];
  189.             }
  190.             else
  191.             {
  192.                 for (int i = 0; i < sum; i++)
  193.                 {
  194.                     if (w[marked[i]] > b[ptr]) continue;
  195.                     events[ptr].push_back(marked[i]);
  196.                 }
  197.                 e.push_back({b[ptr], ptr});
  198.             }
  199.         }
  200.         sort(e.begin(), e.end());
  201.         for (int i = 0; i < n; i++)
  202.         {
  203.             dsu[i] = i;
  204.             sz[i] = 1;
  205.         }
  206.         int _st = -1;
  207.         for (int i = 0; i <= span_len; i++)
  208.         {
  209.             while (_st + 1 < (int) e.size() && (i == span_len || e[_st + 1].first < w[spanning[i]]))
  210.             {
  211.                 _st++;
  212.                 int id = e[_st].second;
  213.                 fst[get(a[id])] = 0;
  214.                 int root = get(a[id]);
  215.                 for (int x : events[id])
  216.                 {
  217.                     int l = get(u[x]);
  218.                     fst[l] = 0;
  219.                     l = get(v[x]);
  220.                     fst[l] = 0;
  221.                 }
  222.                 edge_sz = 1;
  223.                 for (int x : events[id]) {
  224.                     int a = get(u[x]), b = get(v[x]);
  225.                     add(a, b);
  226.                     add(b, a);
  227.                 }
  228.                 tt++;
  229.                 ans[id] = dfs(root);
  230.             }
  231.             if (i == span_len) break;
  232.                uni(u[spanning[i]], v[spanning[i]]);
  233.         }
  234.         int ptr_a = 0, ptr_b = 0;
  235.         for (int i = 0; i < m; i++) {
  236.             int id = ind[i];
  237.             if (bad[id] || flex[id]) {
  238.                 _a[ptr_a++] = id;
  239.             } else {
  240.                 _b[ptr_b++] = id;
  241.             }
  242.         }
  243.         sort(_a, _a + ptr_a, cmp);
  244.         merge(_a, _a + ptr_a, _b, _b + ptr_b, ind, cmp);
  245.     }
  246.     for (int i = 0; i < q; i++)
  247.     {
  248.         if (t[i] == 2)
  249.         {
  250.             cout << ans[i] << '\n';
  251.         }
  252.     }
  253. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement