fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define mp make_pair
  3. #define pb push_back
  4.  
  5. using namespace std;
  6. typedef pair<int,int> pii;
  7. typedef vector<pii> vp;
  8. typedef vector<int> vi;
  9.  
  10. typedef struct DSU{
  11.     vector<int> par,ra;
  12.     int s;
  13.     DSU(int _n) : par(_n+1), ra(_n+1), s(0){
  14.         for(int i=0;i<=_n;i++) par[i]=i;
  15.     }
  16.     int fi(int x){
  17.         while(par[x]!=x) x=par[x];
  18.         return x;
  19.     }
  20.     pii un(int a, int b){
  21.         a=fi(a); b=fi(b);
  22.         if(a==b) return mp(-1,-1);
  23.         if(ra[a]>ra[b]) swap(a,b);
  24.         par[a]=b;
  25.         if(ra[a]==ra[b]) ra[b]++;
  26.         s++;
  27.         return mp(a,b); //a를 b에 합쳤음
  28.     }
  29.     void undo(int a, int b){
  30.         par[a]=a;
  31.         if(ra[b]==ra[a]+1) ra[b]--;
  32.         s--;
  33.     }
  34. }DSU;
  35.  
  36. int n,q;
  37. vector<vp> tree;
  38. DSU uf(300005);
  39.  
  40. void update(int node, int st, int en, int le, int ri, pii e){
  41.     if(ri<st || en<le) return;
  42.     if(le<=st && en<=ri){
  43.         tree[node].pb(e);
  44.         return;
  45.     }
  46.     int mid=(st+en)>>1;
  47.     update(node*2,st,mid,le,ri,e);
  48.     update(node*2+1,mid+1,en,le,ri,e);
  49. }
  50.  
  51. void dfs(int node, int st, int en){
  52.     vector<pii> tv;
  53.     for(pii k : tree[node]){
  54.         tv.push_back(uf.un(k.first,k.second));
  55.     }
  56.     if(st!=en){
  57.         int mid=(st+en)>>1;
  58.         dfs(node*2,st,mid);
  59.         dfs(node*2+1,mid+1,en);
  60.     }
  61.     else{
  62.         printf("%d\n",n-uf.s);
  63.     }
  64.     while(!tv.empty()){
  65.         pii k=tv.back(); tv.pop_back();
  66.         if(k.first==-1) continue;
  67.         uf.undo(k.first,k.second);
  68.     }
  69. }
  70.  
  71. map<pii, int> M;
  72. vector<pair<pii,pii> > query;
  73.  
  74. int main(){
  75.     freopen("connect.in","r",stdin);
  76.     freopen("connect.out","w",stdout);
  77.     scanf("%d %d",&n,&q);
  78.  
  79.     int time=1;
  80.     for(int i=1;i<=q;i++){
  81.         char sel;
  82.         int t1,t2;
  83.         scanf(" %c",&sel);
  84.         if(sel=='?') time++;
  85.         else if(sel=='+' || sel=='-'){
  86.             scanf("%d %d",&t1,&t2);
  87.             if(t1>t2) swap(t1,t2);
  88.             if(M[mp(t1,t2)]){
  89.                 query.emplace_back(mp(t1,t2),mp(M[mp(t1,t2)],time));
  90.                 M[mp(t1,t2)]=0;
  91.             } 
  92.             else M[mp(t1,t2)]=time;
  93.         }
  94.     }
  95.     for(auto it : M){
  96.         if(it.second)
  97.             query.emplace_back(it.first,mp(it.second,time));
  98.     }
  99.     tree.assign(5*(time+2),vp());
  100.     for(auto k : query){
  101.         pii idx=k.first;
  102.         pii life=k.second; life.second--;
  103.         if(life.second<life.first) continue;
  104.         //printf("$%d %d %d %d\n",idx.first,idx.second,life.first,life.second);
  105.         update(1,1,time-1,life.first,life.second,idx);
  106.     }
  107.     dfs(1,1,time-1);
  108.     return 0;
  109. }
  110.  
  111. //ryute:cyanine
Runtime error #stdin #stdout 0s 17584KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/zZbJPc
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!