fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define ull unsigned ll
  7. #define ld long double
  8. typedef vector<int> vi;
  9. typedef multiset<int> mi;
  10. typedef multiset<ll> mll;
  11. typedef vector<ll> vll;
  12. typedef vector<bool> vb;
  13. typedef vector<string> vs;
  14. typedef set<ll> sll;
  15. typedef vector<vector<int>> _2vi;
  16. typedef vector<vector<ll>> _2vll;
  17. #define all(v) ((v).begin()), ((v).end())
  18. #define sz(v) ((ll)((v).size()))
  19.  
  20. #define vinp(v, n)                \
  21.     for (ull i = 0; i < (n); i++) \
  22.     cin >> (v)[i]
  23. #define printv(v)      \
  24.     for (auto i : (v)) \
  25.     cout << i << " "
  26. #define fr0(i, n) for (ull(i) = 0; (i) < (n); (i)++)
  27. #define fr1(i, n) for (ull(i) = 1; (i) < (n); (i)++)
  28. #define fr(i, x, n) for (ull(i) = (x); (i) < (n); (i)++)
  29. #define _CRT_SECURE_NO_WARNING
  30. const ll MOD = 1000000007;
  31.  
  32. void Bustany() {
  33.     ios_base::sync_with_stdio(false);
  34.     cin.tie(NULL);
  35.     cout.tie(NULL);
  36. #ifndef ONLINE_JUDGE
  37.     freopen("./in.txt", "r", stdin), freopen("./out.txt", "w", stdout);
  38. #endif
  39. }
  40.  
  41. const ll N = 1e5 + 5;
  42. vector<sll> adj(N);
  43. //_2vll adj(N,vll(N));
  44. vb vis;
  45.  
  46. ll n, m, q;
  47.  
  48.  
  49. vll values[N];
  50. mll ms;
  51.  
  52. struct dsu {
  53.     vll parent, val;
  54.  
  55.     dsu() {
  56.         parent.resize(n + 1);
  57.         iota(all(parent), 0);
  58.         val.assign(n + 1, 0);
  59.         for (ll i = 0; i < n; i++) {
  60.             val[i + 1] = values[i + 1].back();
  61.             ms.insert(val[i + 1]);
  62.         }
  63.     }
  64.  
  65.     ll find(ll u) {
  66.         if (parent[u] == u)return u;
  67.         return parent[u] = find(parent[u]);
  68.     }
  69.  
  70.     void merge(ll u, ll v) {
  71.         ll f = find(u), s = find(v);
  72.         if (f == s)return;
  73.         ms.erase(ms.find(val[f]));
  74.         ms.erase(ms.find(val[s]));
  75.         parent[f] = s;
  76.         val[s] += val[f];
  77.         ms.insert(val[s]);
  78.     }
  79.  
  80.     ll get(ll u) {
  81.         ll f = find(u);
  82.         return val[f];
  83.     }
  84.  
  85.     void update(ll u) {
  86.         ll f = find(u);
  87.         ll oldv = values[u].back();
  88.         values[u].pop_back();
  89.         ll newv = values[u].back();
  90.         ms.erase(ms.find(val[f]));
  91.         val[f] += (newv - oldv);
  92.         ms.insert(val[f]);
  93.     }
  94.  
  95. };
  96.  
  97.  
  98. void solve() {
  99.     cin >> n >> m >> q;
  100.     vector<pair<ll, ll>> in(m);
  101.     for (ll i = 0; i < n; i++) {
  102.         ll x;
  103.         cin >> x;
  104.         values[i + 1].push_back(x);
  105.     }
  106.     for (ll i = 0; i < m; i++) {
  107.         cin >> in[i].first >> in[i].second;
  108.     }
  109.  
  110.     map<ll, ll> mp;
  111.  
  112.     vector<pair<ll, ll>> queries;
  113.     for (ll i = 0; i < q; i++) {
  114.         char type;
  115.         cin >> type;
  116.         if (type == 'P') {
  117.             ll u, v;
  118.             cin >> u >> v;
  119.             queries.push_back({u, v});
  120.             values[u].push_back(v);
  121.         } else {
  122.             ll u;
  123.             cin >> u;
  124.             queries.push_back({u, -1});
  125.             mp[u]++;
  126.         }
  127.     }
  128.  
  129.  
  130.     dsu d;
  131.     vll ans;
  132.  
  133.     for (ll i = 0; i < m; i++) {
  134.         if (!mp[i + 1]) {
  135.             d.merge(in[i].first, in[i].second);
  136.         }
  137.     }
  138.  
  139.     for (ll i = q - 1; i >= 0; i--) {
  140.         ans.push_back(*ms.rbegin());
  141.         if (queries[i].second == -1) {
  142.             auto [f, s] = queries[i];
  143.             d.merge(in[f - 1].first, in[f - 1].second);
  144.         } else {
  145.             d.update(queries[i].first);
  146.         }
  147.     }
  148.     for (ll i = q - 1; i >= 0; i--) {
  149.         cout << ans[i] << endl;
  150.     }
  151. }
  152.  
  153. int main() {
  154.     Bustany();
  155.     ll t = 1;
  156. //     cin >> t;
  157.     while (t--) {
  158.         solve();
  159.     }
  160. }
Success #stdin #stdout 0.01s 10328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/YLadrP
language:
C++ (gcc 8.3)
created:
21 hours 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!