fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. const int N=3e2+5;
  5. int n,m,q,ans[N];vector<int>adj[N];vector<array<int,2>>ed;vector<vector<int>>seg,add(N),cut(N);
  6. struct dsu
  7. {
  8.     vector<int>parent,group;stack<array<int,4>>st;int res;
  9.     dsu(int n)
  10.     {
  11.         parent=vector<int>(n);
  12.         iota(parent.begin(),parent.end(),0);
  13.         group=vector<int>(n,1);
  14.     }
  15.     int find(int i)
  16.     {
  17.         if(parent[i]==i)
  18.         {
  19.             return i;
  20.         }
  21.         return find(parent[i]);
  22.     }
  23.     bool samegroup(int x,int y)
  24.     {
  25.         return find(x)==find(y);
  26.     }
  27.     void merge(int x,int y)
  28.     {
  29.         int leader1=find(x);
  30.         int leader2=find(y);
  31.         if(group[leader1]>group[leader2])
  32.         {
  33.             swap(leader1,leader2);
  34.         }
  35.         array<int,4>p={0,0,0,0};
  36.         p[0]=leader2,p[1]=group[leader2];
  37.         p[2]=leader1,p[3]=parent[leader1];
  38.         st.push(p);
  39.         if(leader1==leader2)
  40.         {
  41.             return;
  42.         }
  43.         res--;
  44.         group[leader2]+=group[leader1];
  45.         parent[leader1]=leader2;
  46.     }
  47.     void set(int n)
  48.     {
  49.         res=n;
  50.     }
  51.     int getsize(int x)
  52.     {
  53.         return group[find(x)];
  54.     }
  55.     void rollBack()
  56.     {
  57.         if(st.empty())return;
  58.         auto &[a,b,c,d]=st.top();
  59.         st.pop();
  60.         group[a]=b;
  61.         parent[c]=d;
  62.         res+=!samegroup(a,c);
  63.     }
  64.     int getAns()
  65.     {
  66.         return res;
  67.     }
  68. }d(N);
  69. void update(int l,int r,int node,int lx,int rx,int idx)
  70. {
  71.     if(r<lx||l>rx) return;
  72.     if(l>=lx&&r<=rx)
  73.     {
  74.         seg[node].push_back(idx);
  75.         return;
  76.     }
  77.     int mid=l+r>>1;
  78.     update(l,mid,2*node+1,lx,rx,idx);
  79.     update(mid+1,r,2*node+2,lx,rx,idx);
  80. }
  81. void build(int l,int r,int node)
  82. {
  83.     for(auto it:seg[node])
  84.     {
  85.         d.merge(ed[it][0],ed[it][1]);
  86.     }
  87.     if(l==r)
  88.     {
  89.         ans[l]=d.getAns();
  90.         for(auto it:seg[node])
  91.         {
  92.             d.rollBack();
  93.         }
  94.         return;
  95.     }
  96.     int mid=l+r>>1;
  97.     build(l,mid,2*node+1);
  98.     build(mid+1,r,2*node+2);
  99.     for(auto it:seg[node])
  100.     {
  101.         d.rollBack();
  102.     }
  103. }
  104. signed main()
  105. {
  106.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  107.     freopen("connect.in","r",stdin);
  108.     freopen("connect.out","w",stdout);
  109.     cin>>n>>q;
  110.     map<array<int,2>,int>mp;
  111.     ed.push_back({0,0});
  112.     vector<int>queries;
  113.     for(int i=1;i<=q;i++)
  114.     {
  115.         char op;cin>>op;
  116.         if(op=='?')
  117.         {
  118.             queries.push_back(i);
  119.         }
  120.         else
  121.         {
  122.             int a,b;cin>>a>>b;
  123.             if(b>a) swap(a,b);
  124.             if(op=='+')
  125.             {
  126.                 if(!mp.count({a,b}))
  127.                 {
  128.                     ed.push_back({a,b});
  129.                     mp[{a,b}]=ed.size()-1;
  130.                 }
  131.                 int idx=mp[{a,b}];
  132.                 add[idx].push_back(i);
  133.             }
  134.             else
  135.             {
  136.                 int idx=mp[{a,b}];
  137.                 cut[idx].push_back(i);
  138.             }
  139.         }
  140.     }
  141.     for(int i=1;i<ed.size();i++)
  142.     {
  143.         cut[i].push_back(q+1);
  144.     }
  145.     int sz=1;
  146.     while(sz<=q+5) sz<<=1;
  147.     seg=vector<vector<int>>(sz<<1);
  148.     for(int i=1;i<ed.size();i++)
  149.     {
  150.         for(auto it:add[i])
  151.         {
  152.             update(0,sz-1,0,it,*lower_bound(cut[i].begin(),cut[i].end(),it)-1,i);
  153.         }
  154.     }
  155.     d.set(n);
  156.     build(0,sz-1,0);
  157.     for(auto it:queries)
  158.     {
  159.         cout<<ans[it]<<'\n';
  160.     }
  161.     return 0;
  162. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mTtcUK
language:
C++14 (gcc 8.3)
created:
10 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!