fork(1) download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct DSU {
  5.     vector<int> p, sz, hasRoot;
  6.     DSU(int n) : p(n+1), sz(n+1,1), hasRoot(n+1,0) {
  7.         iota(p.begin(), p.end(), 0);
  8.     }
  9.     int find(int x) {
  10.         return p[x] == x ? x : p[x] = find(p[x]);
  11.     }
  12.     void unite(int a, int b, int &blocks, long long &isolated) {
  13.         a = find(a); b = find(b);
  14.         if (a == b) return;
  15.         if (sz[a] < sz[b]) swap(a,b);
  16.         p[b] = a;
  17.         isolated -= (!hasRoot[a] ? sz[a] : 0);
  18.         isolated -= (!hasRoot[b] ? sz[b] : 0);
  19.         blocks -= (!hasRoot[a]);
  20.         blocks -= (!hasRoot[b]);
  21.         sz[a] += sz[b];
  22.         hasRoot[a] |= hasRoot[b];
  23.         isolated += (!hasRoot[a] ? sz[a] : 0);
  24.         blocks += (!hasRoot[a]);
  25.     }
  26.     void activate(int v, int &blocks, long long &isolated) {
  27.         int r = find(v);
  28.         if (!hasRoot[r]) {
  29.             blocks++;
  30.             isolated += sz[r];
  31.         }
  32.     }
  33.     void setRoot(int v, int &blocks, long long &isolated) {
  34.         int r = find(v);
  35.         if (!hasRoot[r]) {
  36.             isolated -= sz[r];
  37.             blocks--;
  38.             hasRoot[r] = 1;
  39.         }
  40.     }
  41. };
  42.  
  43. int main() {
  44.     ios::sync_with_stdio(false);
  45.     cin.tie(nullptr);
  46.     int subtask; cin >> subtask;
  47.     int n,q; cin >> n >> q;
  48.     vector<int> p(n+1);
  49.     for (int i=2;i<=n;i++) cin >> p[i];
  50.     vector<pair<char,int>> queries(q);
  51.     for (int i=0;i<q;i++) cin >> queries[i].first >> queries[i].second;
  52.  
  53.     vector<char> has(n+1,0);
  54.     for (auto &qr : queries) {
  55.         if (qr.first == '+') has[qr.second] = 1;
  56.         else has[qr.second] = 0;
  57.     }
  58.  
  59.     vector<char> active(n+1,0);
  60.     DSU dsu(n);
  61.     int blocks = 0;
  62.     long long isolated = 0;
  63.  
  64.     vector<pair<int,long long>> ans(q);
  65.  
  66.     for (int i=q-1;i>=0;i--) {
  67.         char t = queries[i].first;
  68.         int v = queries[i].second;
  69.         if (t == '+') {
  70.             if (!active[v]) {
  71.                 active[v] = 1;
  72.                 dsu.activate(v,blocks,isolated);
  73.                 if (p[v] && active[p[v]]) dsu.unite(v,p[v],blocks,isolated);
  74.                 for (int u=2;u<=n;u++) if (p[u]==v && active[u]) dsu.unite(v,u,blocks,isolated);
  75.                 if (v == 1) dsu.setRoot(v,blocks,isolated);
  76.             }
  77.         } else {
  78.             if (active[v]) {
  79.                 dsu.activate(v,blocks,isolated);
  80.                 if (p[v] && active[p[v]]) dsu.unite(v,p[v],blocks,isolated);
  81.                 for (int u=2;u<=n;u++) if (p[u]==v && active[u]) dsu.unite(v,u,blocks,isolated);
  82.                 if (v == 1) dsu.setRoot(v,blocks,isolated);
  83.                 active[v] = 0;
  84.             }
  85.         }
  86.         ans[i] = {blocks, isolated};
  87.     }
  88.  
  89.     for (int i=0;i<q;i++) cout << ans[i].first << " " << ans[i].second << "\n";
  90. }
  91.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
3
10 5
1 2 2 2 1 6 7 7 6
+ 9
+ 7
+ 2
- 9
- 7
stdout 
2 3
2 2
1 1
0 0
0 0
https://ideone.com/snz12p
language:
C++14 (clang 8.0)
created:
1 day 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!