제출 #146051

#제출 시각아이디문제언어결과실행 시간메모리
146051Bodo171다리 (APIO19_bridges)C++14
59 / 100
3058 ms27264 KiB
#include <iostream> #include <fstream> #include <vector> #include <algorithm> #include <map> using namespace std; const int nmax=100005; const int buck=600; struct event { int tip,id; }ev; vector<event> evs[2*nmax]; vector<int> spec,norm; 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]; int ops,n,m,q,i,nr,j,sum; 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); ++ops; mic[ops]=B;mare[ops]=A; tt[B]=A;rg[A]+=rg[B]; } void rollback(int lim) { while(ops>lim) { tt[mic[ops]]=mic[ops]; rg[mare[ops]]-=rg[mic[ops]]; ops--; } } void add(int x,int y) { ad[x].push_back(y); ad[y].push_back(x); } void res(int x) { ad[x].clear(); viz[x]=0; } void dfs(int x) { viz[x]=1;sum+=rg[x]; for(int it=0;it<ad[x].size();it++) if(!viz[ad[x][it]]) dfs(ad[x][it]); } 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()); int 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]]; for(int bg=1;bg<=q;bg+=buck) { nr=0; ops=0; spec.clear(); for(i=1;i<=n;i++) tt[i]=i,rg[i]=1; for(i=bg;i<min(bg+buck,q+1);i++) { if(tip[i]==1) { spec.push_back(wh[i]); ap[wh[i]]=1; ini[wh[i]]=w[wh[i]]; } else { evs[cost[i]].push_back({1,i}); } } for(i=1;i<=m;i++) if(!ap[i]) evs[w[i]].push_back({0,i}); int sz; for(i=lim;i>=1;i--) { sz=evs[i].size(); for(int it=sz-1;it>=0;it--) { ev=evs[i][it]; if(ev.tip==0) unite(finds(a[ev.id]),finds(b[ev.id])); else { /* int ind=ev.id; for(j=bg; j<ind; j++) if(tip[j]==1) { w[wh[j]]=cost[j]; } for(j=0; j<spec.size(); j++) if(w[spec[j]]>=i) add(finds(a[spec[j]]),finds(b[spec[j]])); sum=0; dfs(finds(wh[ind])); ans[ind]=sum; for(j=0; j<spec.size(); j++) { res(finds(a[spec[j]])); res(finds(b[spec[j]])); } for(j=bg; j<ind; j++) if(tip[j]==1) { w[wh[j]]=ini[wh[j]]; }*/ int ind=ev.id,de_unde=ops; for(j=bg; j<ind; j++) if(tip[j]==1) { w[wh[j]]=cost[j]; } for(j=0; j<spec.size(); j++) if(w[spec[j]]>=i) { unite(finds(a[spec[j]]),finds(b[spec[j]])); } ans[ind]=rg[finds(wh[ind])]; rollback(de_unde); for(j=bg; j<ind; j++) if(tip[j]==1) { w[wh[j]]=ini[wh[j]]; } } } } for(i=1;i<=lim;i++) evs[i].resize(0); for(i=bg;i<min(bg+buck,q+1);i++) if(tip[i]==1) w[wh[i]]=cost[i]; for(i=0;i<spec.size();i++) ap[spec[i]]=0; } for(i=1;i<=q;i++) if(tip[i]==2) cout<<ans[i]<<'\n'; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

bridges.cpp: In function 'int finds(int)':
bridges.cpp:21:9: warning: unused variable 'y' [-Wunused-variable]
     int y=x,aux;
         ^
bridges.cpp:21:13: warning: unused variable 'aux' [-Wunused-variable]
     int y=x,aux;
             ^~~
bridges.cpp: In function 'void dfs(int)':
bridges.cpp:62:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int it=0;it<ad[x].size();it++)
                  ~~^~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:85:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<norm.size();i++)
             ~^~~~~~~~~~~~
bridges.cpp:153:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for(j=0; j<spec.size(); j++)
                              ~^~~~~~~~~~~~
bridges.cpp:173: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...