Submission #244356

#TimeUsernameProblemLanguageResultExecution timeMemory
244356MvCCollapse (JOI18_collapse)C++11
5 / 100
15089 ms16476 KiB
#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include "collapse.h" #include <bits/stdc++.h> #define rc(x) return cout<<x<<endl,0 #define pb push_back #define mkp make_pair #define in insert #define er erase #define fd find #define fr first #define sc second #define all(x) x.begin(),x.end() #define lun(x) (int)x.size() typedef long long ll; typedef long double ld; const ll INF=0x3f3f3f3f3f3f3f3f; const ll llinf=(1LL<<60); const int inf=(1<<30); const int nmax=1e5+50; const int mg=5000; const ll mod=1e9+7; using namespace std; int n,c,q,t,i,j,x,y,ai,bi,er,p[nmax],sz[nmax],v[nmax]; vector<pair<pair<int,int>,pair<int,int> > >rl,ed[nmax],vc,a,b; vector<pair<pair<int,int>,int> >qr[nmax]; set<pair<int,int> >s; vector<int>rs; set<pair<int,int> >::iterator it; int fnd(int x) { if(p[x]==x)return x; return p[x]=fnd(p[x]); } void uni(int x,int y,int k) { x=fnd(x),y=fnd(y); if(x==y)return; if(sz[x]<sz[y])swap(x,y); if(k)rl.pb(mkp(mkp(y,p[y]),mkp(x,sz[x]))); p[y]=x; sz[x]+=sz[y]; er++; } vector<int> simulateCollapse(int N,vector<int> T,vector<int> X,vector<int> Y,vector<int> W,vector<int> P) { n=N,c=lun(T),q=lun(W); for(i=0;i<c;i++) { t=T[i],x=X[i],y=Y[i]; x++,y++; if(y>x)swap(x,y); ed[i/mg].pb(mkp(mkp(x,y),mkp(t,i))); } for(i=0;i<q;i++) { x=W[i],y=P[i]; y++; qr[x/mg].pb(mkp(mkp(y,x%mg),i)); } rs.resize(q,0); for(i=0;i<=c/mg;i++) { if(qr[i].empty())break; sort(all(qr[i])); for(j=1;j<=n;j++) { p[j]=j; sz[j]=1; } for(j=0;j<c;j++) { v[j]=0; } vc.clear(),a.clear(),b.clear(); for(j=0;j<i;j++)for(t=0;t<lun(ed[j]);t++)vc.pb(ed[j][t]); sort(all(vc)); for(j=0;j<lun(vc);j++) { v[vc[j].sc.sc]^=1; } for(j=0;j<lun(ed[i]);j++) { if(v[ed[i][j].sc.sc]) { b.pb(ed[i][j]); v[ed[i][j].sc.sc]=0; } } for(j=0;j<lun(vc);j++)if(v[vc[j].sc.sc])a.pb(vc[j]),v[vc[j].sc.sc]=0; ai=0; er=0; for(j=0;j<lun(qr[i]);j++) { for(;ai<lun(a);ai++) { if(a[ai].fr.fr>qr[i][j].fr.fr)break; uni(a[ai].fr.fr,a[ai].fr.sc,0); } s.clear(); for(bi=0;bi<lun(b);bi++) { if(b[bi].fr.fr>qr[i][j].fr.fr)break; s.in(b[bi].fr); } for(t=0;t<=qr[i][j].fr.sc;t++) { if(ed[i][t].fr.fr>qr[i][j].fr.fr)continue; if(s.fd(ed[i][t].fr)!=s.end())s.er(s.fd(ed[i][t].fr)); else s.in(ed[i][t].fr); } rl.clear(); for(it=s.begin();it!=s.end();it++)uni(it->fr,it->sc,1); rs[qr[i][j].sc]=qr[i][j].fr.fr-er; reverse(all(rl)); for(t=0;t<lun(rl);t++) { p[rl[t].fr.fr]=rl[t].fr.sc; sz[rl[t].sc.fr]=rl[t].sc.sc; } er-=lun(rl); } for(j=1;j<=n;j++) { p[j]=j; sz[j]=1; } for(j=0;j<lun(a);j++)swap(a[j].fr.fr,a[j].fr.sc); for(j=0;j<lun(b);j++)swap(b[j].fr.fr,b[j].fr.sc); sort(all(a)); sort(all(b)); reverse(all(a)); reverse(all(b)); reverse(all(qr[i])); ai=0; er=0; for(j=0;j<lun(qr[i]);j++) { for(;ai<lun(a);ai++) { if(a[ai].fr.fr<=qr[i][j].fr.fr)break; uni(a[ai].fr.fr,a[ai].fr.sc,0); } s.clear(); for(bi=0;bi<lun(b);bi++) { if(b[bi].fr.fr<=qr[i][j].fr.fr)break; s.in(b[bi].fr); } for(t=0;t<=qr[i][j].fr.sc;t++) { if(ed[i][t].fr.sc<=qr[i][j].fr.fr)continue; if(s.fd(mkp(ed[i][t].fr.sc,ed[i][t].fr.fr))!=s.end())s.er(s.fd(mkp(ed[i][t].fr.sc,ed[i][t].fr.fr))); else s.in(mkp(ed[i][t].fr.sc,ed[i][t].fr.fr)); } rl.clear(); for(it=s.begin();it!=s.end();it++)uni(it->fr,it->sc,1); rs[qr[i][j].sc]+=n-qr[i][j].fr.fr-er; reverse(all(rl)); for(t=0;t<lun(rl);t++) { p[rl[t].fr.fr]=rl[t].fr.sc; sz[rl[t].sc.fr]=rl[t].sc.sc; } er-=lun(rl); } } return rs; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...