Submission #1059518

#TimeUsernameProblemLanguageResultExecution timeMemory
1059518heeewTelephone Plans (CCO24_day2problem3)C++14
25 / 25
1444 ms108400 KiB
#include<iostream> #include<algorithm> #include<vector> #include<set> using namespace std; using lint = long long; using vint = vector<int>; using pii = pair<int,int>; const int MAX_N=500010; const int MAX_Q=1500010; struct Obj { int v,p,i; }; int in,n,q; set<int> edge[MAX_N]; int cidx=0; int cnt[MAX_N<<1]; int col[MAX_N<<1]; lint sum[MAX_Q],sump[MAX_Q]; int getmin(int x,int y) { vector<Obj> vx={{x,y,-1}},vy={{y,x,-1}}; while(1) { while(!vx.empty()) { auto p=vx.back(); auto it=edge[p.v].upper_bound(p.i); if(it==edge[p.v].end()) { vx.pop_back(); continue; } int v=vx.back().i=*it; if(v==p.p)continue; vx.push_back({v,p.v,-1}); break; } if(vx.empty())return x; while(!vy.empty()) { auto p=vy.back(); auto it=edge[p.v].upper_bound(p.i); if(it==edge[p.v].end()) { vy.pop_back(); continue; } int v=vy.back().i=*it; if(v==p.p)continue; vy.push_back({v,p.v,-1}); break; } if(vy.empty())return y; } return x; } void colorall(int v,int p,int c) { cnt[col[v]]--; col[v]=c; cnt[col[v]]++; for(auto v0 : edge[v]) if(v0!=p) colorall(v0,v,c); } int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin >> in >> n >> q; for(int i=0;i<n;i++) { col[i+1]=i; cnt[i]=1; } cidx=n; lint lasta=0,change=0; for(int i=1;i<=q;i++) { int o; lint x,y,t; cin >> o; if(o==1) { cin >> x >> y; if(in)x^=lasta,y^=lasta; if(x>y)swap(x,y); change=(lint)cnt[col[x]]*cnt[col[y]]; if(cnt[col[x]]<cnt[col[y]]) colorall(x,y,col[y]); else colorall(y,x,col[x]); edge[x].insert(y); edge[y].insert(x); } if(o==2) { cin >> x >> y; if(in)x^=lasta,y^=lasta; edge[x].erase(y); edge[y].erase(x); if(getmin(x,y)==x) colorall(x,y,cidx++); else colorall(y,x,cidx++); change=-(lint)cnt[col[x]]*cnt[col[y]]; } if(o==3)change=0; sum[i]=sum[i-1]+change; sump[i]=sump[i-1]+max(0LL,change); if(o==3) { cin >> t; if(in)t^=lasta; int j=max(0LL,i-t); lasta=sum[j]+sump[i]-sump[j]; cout << lasta << '\n'; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...