fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct DSU {
  5.     vector<int> p, sz, hasRoot;
  6.     int blocks;
  7.     long long isolated;
  8.     DSU(int n) : p(n+1), sz(n+1,0), hasRoot(n+1,0), blocks(0), isolated(0) {
  9.         iota(p.begin(), p.end(), 0);
  10.     }
  11.     int find(int x){ return p[x]==x?x:p[x]=find(p[x]); }
  12.     void make_set(int x,bool isRoot){
  13.         p[x]=x; sz[x]=1; hasRoot[x]=isRoot;
  14.         if(!isRoot){ blocks++; isolated++; }
  15.     }
  16.     void unite(int a,int b){
  17.         a=find(a); b=find(b);
  18.         if(a==b) return;
  19.         if(sz[a]<sz[b]) swap(a,b);
  20.         p[b]=a;
  21.         if(!hasRoot[a]){ blocks--; isolated-=sz[a]; }
  22.         if(!hasRoot[b]){ blocks--; isolated-=sz[b]; }
  23.         sz[a]+=sz[b];
  24.         hasRoot[a]|=hasRoot[b];
  25.         if(!hasRoot[a]){ blocks++; isolated+=sz[a]; }
  26.     }
  27. };
  28.  
  29. int main(){
  30.     ios::sync_with_stdio(false);
  31.     cin.tie(nullptr);
  32.     int sub; cin>>sub;
  33.     int n,q; cin>>n>>q;
  34.     vector<int> par(n+1);
  35.     for(int i=2;i<=n;i++) cin>>par[i];
  36.     vector<pair<char,int>> ops(q);
  37.     for(int i=0;i<q;i++) cin>>ops[i].first>>ops[i].second;
  38.  
  39.     vector<char> finalActive(n+1,0);
  40.     for(auto [t,v]:ops){
  41.         if(t=='+') finalActive[v]=1;
  42.         else finalActive[v]=0;
  43.     }
  44.  
  45.     DSU dsu(n);
  46.     vector<char> active(n+1,0);
  47.     for(int i=1;i<=n;i++) if(finalActive[i]){
  48.         dsu.make_set(i,i==1);
  49.         active[i]=1;
  50.     }
  51.     for(int i=2;i<=n;i++) if(active[i] && active[par[i]]) dsu.unite(i,par[i]);
  52.  
  53.     vector<pair<int,long long>> ans(q);
  54.     for(int i=q-1;i>=0;i--){
  55.         ans[i]={dsu.blocks,dsu.isolated};
  56.         char t=ops[i].first; int v=ops[i].second;
  57.         if(t=='-'){
  58.             if(!active[v]){
  59.                 active[v]=1;
  60.                 dsu.make_set(v,v==1);
  61.                 if(par[v] && active[par[v]]) dsu.unite(v,par[v]);
  62.                 for(int u=2;u<=n;u++) if(par[u]==v && active[u]) dsu.unite(v,u);
  63.             }
  64.         }else{
  65.             // '+ v' in forward => do nothing here (we already had it active)
  66.         }
  67.     }
  68.     for(auto [a,b]:ans) cout<<a<<" "<<b<<"\n";
  69. }
  70.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
3
10 5
1 2 2 2 1 6 7 7 6
+ 9
+ 7
+ 2
- 9
- 7
stdout
copy 
2 3
2 3
2 3
2 2
1 1
https://ideone.com/crotDH
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!