fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long 
  5. #define fi first
  6. #define se second
  7. #define pii pair<int,int>
  8. #define pll pair<ll,ll>
  9. #define el '\n'
  10. #define pb push_back
  11.  
  12. const int maxN = 2e5 + 5;
  13. const int maxM = 2e5 + 5;
  14.  
  15. int n, m, query_count;
  16. ll a[maxN];
  17.  
  18. struct Edge {
  19.     int u, v;
  20. } dsc[maxM];
  21.  
  22. struct Query {
  23.     int type;
  24.     int id;      // for type 1
  25.     int u;       // for type 2
  26.     ll val;      // for type 2 (new value)
  27.     ll old_val;  // for type 2 (value before update)
  28. };
  29.  
  30. Query q[maxN];
  31. bool deleted_bridge[maxM];
  32.  
  33. int parent_node[maxN];
  34. ll comp_sum[maxN];
  35. multiset<ll> comp_multiset;
  36.  
  37. int find_root(int i) {
  38.     if (parent_node[i] == i)
  39.         return i;
  40.     return parent_node[i] = find_root(parent_node[i]);
  41. }
  42.  
  43. void union_sets(int u, int v) {
  44.     int root_u = find_root(u);
  45.     int root_v = find_root(v);
  46.     if (root_u != root_v) {
  47.         comp_multiset.erase(comp_multiset.find(comp_sum[root_u]));
  48.         comp_multiset.erase(comp_multiset.find(comp_sum[root_v]));
  49.  
  50.         parent_node[root_u] = root_v;
  51.         comp_sum[root_v] += comp_sum[root_u];
  52.  
  53.         comp_multiset.insert(comp_sum[root_v]);
  54.     }
  55. }
  56.  
  57. int main() {
  58.     ios_base::sync_with_stdio(0); 
  59.     cin.tie(0);
  60.  
  61.     if (!(cin >> n >> m >> query_count)) return 0;
  62.  
  63.     for (int i = 1; i <= n; i++) {
  64.         cin >> a[i];
  65.     }
  66.  
  67.     for (int i = 1; i <= m; i++) {
  68.         cin >> dsc[i].u >> dsc[i].v;
  69.     }
  70.  
  71.     for (int i = 1; i <= query_count; i++) {
  72.         cin >> q[i].type;
  73.         if (q[i].type == 1) {
  74.             cin >> q[i].id;
  75.             deleted_bridge[q[i].id] = true;
  76.         } else if (q[i].type == 2) {
  77.             cin >> q[i].u >> q[i].val;
  78.         }
  79.     }
  80.  
  81.     vector<ll> curr_a(n + 1);
  82.     for (int i = 1; i <= n; i++) curr_a[i] = a[i];
  83.  
  84.     for (int i = 1; i <= query_count; i++) {
  85.         if (q[i].type == 2) {
  86.             q[i].old_val = curr_a[q[i].u];
  87.             curr_a[q[i].u] = q[i].val;
  88.         }
  89.     }
  90.  
  91.     for (int i = 1; i <= n; i++) {
  92.         parent_node[i] = i;
  93.         comp_sum[i] = curr_a[i];
  94.     }
  95.  
  96.     for (int i = 1; i <= m; i++) {
  97.         if (!deleted_bridge[i]) {
  98.             int root_u = find_root(dsc[i].u);
  99.             int root_v = find_root(dsc[i].v);
  100.             if (root_u != root_v) {
  101.                 parent_node[root_u] = root_v;
  102.                 comp_sum[root_v] += comp_sum[root_u];
  103.             }
  104.         }
  105.     }
  106.  
  107.     for (int i = 1; i <= n; i++) {
  108.         if (parent_node[i] == i) {
  109.             comp_multiset.insert(comp_sum[i]);
  110.         }
  111.     }
  112.  
  113.     vector<ll> answers;
  114.     for (int i = query_count; i >= 1; i--) {
  115.         if (q[i].type == 3) {
  116.             answers.push_back(*comp_multiset.rbegin());
  117.         } else if (q[i].type == 2) {
  118.             int u = q[i].u;
  119.             ll old_val = q[i].old_val;
  120.             ll new_val = q[i].val;
  121.  
  122.             int root = find_root(u);
  123.             comp_multiset.erase(comp_multiset.find(comp_sum[root]));
  124.             curr_a[u] = old_val;
  125.             comp_sum[root] += (old_val - new_val);
  126.             comp_multiset.insert(comp_sum[root]);
  127.         } else if (q[i].type == 1) {
  128.             int id = q[i].id;
  129.             union_sets(dsc[id].u, dsc[id].v);
  130.         }
  131.     }
  132.  
  133.     for (int i = (int)answers.size() - 1; i >= 0; i--) {
  134.         cout << answers[i] << el;
  135.     }
  136.  
  137.     return 0;
  138. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mqPbLu
language:
C++ (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!