Advertisement
Guest User

300iq APIO B

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