Submission #756650

#TimeUsernameProblemLanguageResultExecution timeMemory
756650khoquennguoiminhthuongBridges (APIO19_bridges)C++17
44 / 100
3035 ms11616 KiB
#include <bits/stdc++.h> using namespace std; int n,m,q; struct canh { int u,v,w; } e[500005]; struct roll { int type,u,pa; }; int goc[500005]; int sz[500005]; int dd[500005]; stack<pair<int,pair<int,int>>>st; void gop(int u,int v,int type) { st.push({type,{u,goc[u]}}); goc[u]=v; } int ans[500005]; int gopgoc(int u) { if(goc[u]==0)return u; gop(u,gopgoc(goc[u]),0); return goc[u]; } void add(int u,int v) { u=gopgoc(u); v=gopgoc(v); if(u==v)return ; sz[u]+=sz[v]; gop(v,u,1); } void rollback(int k) { while(st.size()>k) { pair<int,pair<int,int>>vv=st.top(); st.pop(); if(vv.first==1)sz[goc[vv.second.first]]-=sz[vv.second.first]; goc[vv.second.first]=vv.second.second; } } bool cmp(int a,int b) { if(e[a].w!=e[b].w)return e[a].w>e[b].w; return a<b; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m; for(int i=1; i<=m; i++) { cin>>e[i].u>>e[i].v>>e[i].w; } for(int i=1; i<=n; i++)sz[i]=1; cin>>q; for(int i=1; i<=q; i++) cin>>e[i+m].u>>e[i+m].v>>e[i+m].w; int blsize=1500; for(int l=m+1; l<=q+m; l+=blsize) { int r=min(l+blsize-1,m+q); rollback(0); vector<int>change; vector<int>unchange; for(int i=l; i<=r; i++) { if(e[i].u==1) { change.push_back(i); dd[e[i].v]=1; } else unchange.push_back(i); } for(int i=1; i<=m; i++)if(dd[i]==0)unchange.push_back(i); else dd[i]=0; sort(unchange.begin(),unchange.end(),cmp); reverse(change.begin(),change.end()); for(auto v:unchange) { if(v<=m) { add(e[v].u,e[v].v); } else { int now=st.size(); for(auto vv:change) { if(vv<=v&&dd[e[vv].v]==0) { dd[e[vv].v]=1; int id=e[vv].v; if(e[vv].w>=e[v].w)add(e[id].u,e[id].v); } } for(auto vv:change) { if(vv>v&&dd[e[vv].v]==0) { int id=e[vv].v; if(e[id].w>=e[v].w)add(e[id].u,e[id].v); } } ans[v]=sz[gopgoc(e[v].v)]; rollback(now); for(auto vv:change)dd[e[vv].v]=0; } } for(int i=l;i<=r;i++)if(e[i].u==1){int id=e[i].v;e[id].w=e[i].w;} } for(int i=m+1; i<=m+q; i++)if(ans[i])cout<<ans[i]<<'\n'; return 0; }

Compilation message (stderr)

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:33:20: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |     while(st.size()>k) {
      |           ~~~~~~~~~^~
#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...