Submission #146625

#TimeUsernameProblemLanguageResultExecution timeMemory
146625Bodo171Bridges (APIO19_bridges)C++14
60 / 100
3010 ms24968 KiB
#include <iostream> #include <fstream> #include <vector> #include <algorithm> #include <map> #include <cassert> using namespace std; const int nmax=100005; const int buck=200; struct event { int tip,id,c; }ev,evs[2*nmax+2*buck],niu[2*nmax+2*buck]; bool comp(event unu,event doi) { if(unu.c==doi.c) return unu.tip>doi.tip; return unu.c<doi.c; } vector<int> spec,norm,mods; vector<int> ad[nmax]; map<int,int> act; int tt[nmax],rg[nmax],mic[nmax],mare[nmax],a[nmax],b[nmax],w[nmax],tip[nmax],wh[nmax],cost[nmax],ap[nmax],ans[nmax],ini[nmax],viz[nmax],ps[2*nmax]; int nxt[2*nmax],ce[2*nmax],cap[2*nmax]; int ops,n,m,q,i,nr,j,sum,lim,tot; int finds(int x) { int y=x,aux; while(x!=tt[x]) x=tt[x]; while(y!=x) { aux=tt[y]; tt[y]=x; y=aux; } return x; } void unite(int A,int B) { if(A==B) return; if(rg[A]<rg[B]) swap(A,B); tt[B]=A;rg[A]+=rg[B]; } void baga(int a,int b) { nxt[cap[a]]=++tot; cap[a]=tot; ce[tot]=b; } void add(int x,int y) { baga(x,y); baga(y,x); } void res(int x) { cap[x]=x; nxt[x]=0; viz[x]=0; } void dfs(int x) { viz[x]=1;sum+=rg[x]; for(int it=nxt[x];it!=0;it=nxt[it]) if(!viz[ce[it]]) dfs(ce[it]); } void mysort() { for(i=1;i<=nr;i++) ps[evs[i].c]++; for(i=1;i<=lim;i++) ps[i]+=ps[i-1]; for(i=1;i<=nr;i++) niu[++ps[evs[i].c-1]]=evs[i]; for(i=0;i<=lim;i++) ps[i]=0; } int main() { //freopen("data.in","r",stdin); ios_base::sync_with_stdio(false); cin>>n>>m; for(i=1;i<=m;i++) { cin>>a[i]>>b[i]>>w[i]; norm.push_back(w[i]); } cin>>q; for(i=1;i<=q;i++) { cin>>tip[i]>>wh[i]>>cost[i]; norm.push_back(cost[i]); } sort(norm.begin(),norm.end()); norm.erase(unique(norm.begin(),norm.end()),norm.end()); lim=norm.size(); for(i=0;i<norm.size();i++) act[norm[i]]=i+1; for(i=1;i<=m;i++) w[i]=act[w[i]]; for(i=1;i<=q;i++) cost[i]=act[cost[i]]; int bg=0; tot=n; for(i=1;i<=n;i++) cap[i]=i; for(bg=1;bg<=q;bg++) { nr=0; ops=0; spec.resize(0);mods.resize(0); for(i=1;i<=n;i++) tt[i]=i,rg[i]=1; for(i=bg;i<=q&&mods.size()<buck;i++) { if(tip[i]==1) { spec.push_back(wh[i]); ap[wh[i]]=1; ini[wh[i]]=w[wh[i]]; mods.push_back(i); } else { evs[++nr]={1,i,cost[i]}; } } i--;int en=i; for(i=1;i<=m;i++) if(!ap[i]) evs[++nr]={0,i,w[i]}; mysort(); for(i=nr;i>=1;i--) { ev=niu[i]; if(ev.tip==0) unite(finds(a[ev.id]),finds(b[ev.id])); else { int ind=ev.id; tot=n; for(j=0; j<mods.size()&&mods[j]<=ind; j++) w[wh[mods[j]]]=cost[mods[j]]; for(j=0; j<spec.size(); j++) if(w[spec[j]]>=ev.c) add(finds(a[spec[j]]),finds(b[spec[j]])); sum=0; dfs(finds(wh[ind])); ans[ind]=sum; res(finds(wh[ind])); for(j=0; j<spec.size(); j++) { res(finds(a[spec[j]])); res(finds(b[spec[j]])); w[spec[j]]=ini[spec[j]]; } for(int p=n+1;p<=tot;p++) nxt[p]=ce[p]=0; } } for(i=bg;i<=en;i++) if(tip[i]==1) w[wh[i]]=cost[i]; for(i=0;i<spec.size();i++) ap[spec[i]]=0; bg=en; } for(i=1;i<=q;i++) if(tip[i]==2) cout<<ans[i]<<'\n'; return 0; }

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:98:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<norm.size();i++)
             ~^~~~~~~~~~~~
bridges.cpp:143:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(j=0; j<mods.size()&&mods[j]<=ind; j++)
                          ~^~~~~~~~~~~~
bridges.cpp:145:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(j=0; j<spec.size(); j++)
                          ~^~~~~~~~~~~~
bridges.cpp:152:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(j=0; j<spec.size(); j++)
                          ~^~~~~~~~~~~~
bridges.cpp:165:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0;i<spec.size();i++)
                 ~^~~~~~~~~~~~
#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...