Submission #146573

#TimeUsernameProblemLanguageResultExecution timeMemory
146573usernameBridges (APIO19_bridges)C++14
44 / 100
3035 ms9848 KiB
#pragma GCC optimize("O3") #include<bits/stdc++.h> using namespace std; typedef pair<int,int> pii; #define REP(i,j,k) for(register int i=(j);i<(k);++i) #define RREP(i,j,k) for(register int i=int(j)-1;i>=(k);--i) #define ALL(a) a.begin(),a.end() #define pb push_back #define F first #define S second #define endl '\n' #define IOS cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(false) struct tup{int F,S,T;}; const int maxn=5e4+9,maxm=1e5+9,maxq=1e5+9,bl=660; int n,m,q,fa[maxn],sz[maxn],res[maxq]; tup eds[maxm],qrs[maxq]; set<pii>st; vector<pii>rf,rs; vector<int>p; bitset<maxm>mrk; void init(int k){REP(i,0,k)fa[i]=i,sz[i]=1;} int find(int x,bool r){ if(x==fa[x])return x; else{ if(r)rf.pb({x,fa[x]}); return fa[x]=find(fa[x],r); } } void unite(int x,int y,bool r){ x=find(x,r),y=find(y,r); if(x==y)return; if(sz[x]>sz[y])swap(x,y); if(r)rf.pb({x,fa[x]}),rs.pb({y,sz[y]}); fa[x]=y,sz[y]+=sz[x]; } void restore(){ RREP(i,rf.size(),0)fa[rf[i].F]=rf[i].S; RREP(i,rs.size(),0)sz[rs[i].F]=rs[i].S; } main(){ IOS; cin>>n>>m; REP(i,0,m){ int u,v,w;cin>>u>>v>>w,--u,--v,w=-w; eds[i]={u,v,w}; st.insert({w,i}); } cin>>q; REP(i,0,q)cin>>qrs[i].F>>qrs[i].S>>qrs[i].T,--qrs[i].S,qrs[i].T=-qrs[i].T; for(int l=0;l<q;l+=bl){ int r=min(l+bl,q); p.clear(); REP(i,l,r)if(qrs[i].F==2)p.pb(i); sort(ALL(p),[](int a,int b){return qrs[a].T<qrs[b].T;}); init(n); auto it=st.begin(); REP(i,0,p.size()){ REP(i,l,r)if(qrs[i].F==1)mrk[qrs[i].S]=1; tup&qq=qrs[p[i]]; while(it!=st.end()&&it->F<=qq.T){ if(!mrk[it->S])unite(eds[it->S].F,eds[it->S].S,0); ++it; } rf.clear(),rs.clear(); RREP(j,p[i],l){ tup&tq=qrs[j]; if(tq.F==1&&mrk[tq.S]){ if(tq.T<=qq.T)unite(eds[tq.S].F,eds[tq.S].S,1); mrk[tq.S]=0; } } REP(j,p[i],r){ tup&tq=qrs[j]; if(tq.F==1&&mrk[tq.S]){ if(eds[tq.S].T<=qq.T)unite(eds[tq.S].F,eds[tq.S].S,1); mrk[tq.S]=0; } } res[p[i]]=sz[find(qq.S,1)]; restore(); } REP(i,l,r){ tup&qq=qrs[i]; if(qq.F==1){ auto it=st.find({eds[qq.S].T,qq.S}); st.erase(it); st.insert({eds[qq.S].T=qq.T,qq.S}); } } } REP(i,0,q)if(qrs[i].F==2)cout<<res[i]<<endl; }

Compilation message (stderr)

bridges.cpp:46:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
bridges.cpp: In function 'int main()':
bridges.cpp:5:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(register int i=(j);i<(k);++i)
                                            ^
bridges.cpp:63:3: note: in expansion of macro 'REP'
   REP(i,0,p.size()){
   ^~~
#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...