Submission #128235

#TimeUsernameProblemLanguageResultExecution timeMemory
128235fefeBridges (APIO19_bridges)C++17
0 / 100
3067 ms4688 KiB
#include<bits/stdc++.h> #define MAX_N 500005 #define MAX_M 1000005 #define fi first #define se second #define pb push_back #define eb emplace_back #define all(v) (v).begin(),(v).end() using namespace std; typedef long long LL; typedef long double LD; typedef pair<int,int> pii; typedef pair<LL,LL> pil; struct edge{ int x,y,v; }E[MAX_M],Q[MAX_M]; struct node{ int t,i,b,a; }; struct infor{ int x,y,hx,hy,ex,ey; }; int n,m; int qn; int par[MAX_N],height[MAX_N],ea[MAX_N]; bool chk[MAX_M]; const int b=300; vector<edge> e; vector<node> lst; vector<pii> ans; stack<infor> st; int find_par(int x){return par[x]==x?x:find_par(par[x]);} void init(){ for(int i=1;i<=n;i++){ par[i]=i; height[i]=ea[i]=1; } } int merge(int x,int y){ int p=find_par(x); int q=find_par(y); if(p==q) return 0; st.push({p,q,height[p],height[q],ea[p],ea[q]}); if(height[p]>height[q]){ ea[p]+=ea[q]; par[q]=p; }else{ if(height[p]==height[q]) height[q]++; ea[q]+=ea[p]; par[p]=q; } return 1; } void _back(int cnt){ while(st.size() && cnt--){ infor p = st.top(); par[p.x]=p.x;par[p.y]=p.y; height[p.x]=p.hx;height[p.y]=p.hy; ea[p.x]=p.ex;ea[p.y]=p.ey; st.pop(); } while(st.size()) st.pop(); } void solve(int k){ for(int i=1;i<=m;i++) chk[i]=false; for(int i=0;i<qn;i++){ if(Q[i].v==1){ chk[Q[i].x]=true; lst.pb({i,Q[i].x,E[Q[i].x].v,Q[i].y}); Q[i].v=-1; }else Q[i].v=i; } e.clear();e.resize(0); for(int i=1;i<=m;i++){ if(!chk[i]) e.pb(E[i]); } sort(Q,Q+qn,[&](const edge x,const edge y){ if(x.v==-1) return false; if(y.v==-1) return true; return (x.y>y.y); }); sort(all(e),[&](const edge x,const edge y){return x.v>y.v;}); init(); int p=0; for(int i=0;i<qn;i++){ edge ques = Q[i]; if(ques.v==-1) break; int cn=0; int eee=e.size(); for(;p<eee && e[p].v>=ques.y;p++) merge(e[p].x,e[p].y); for(node ne:lst){ int x=E[ne.i].x; int y=E[ne.i].y; int v; if(ne.t>ques.v) v=ne.b; else v=ne.a; if(v>=ques.y) cn+=merge(x,y); } ans.pb({k+ques.v,ea[find_par(ques.x)]}); _back(cn); } for(node ne:lst) E[ne.i].v=ne.a; qn=0; } int main(){ int i; scanf("%d %d",&n,&m); for(i=1;i<=m;i++) scanf("%d %d %d",&E[i].x,&E[i].y,&E[i].v); int q;scanf("%d",&q); for(i=1;i<=q;i++){ scanf("%d %d %d",&Q[qn].v,&Q[qn].x,&Q[qn].y);qn++; if(qn==b) solve(i); } solve(i); sort(all(ans)); for(pii print:ans) printf("%d\n",print.se); return 0; }

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:109:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
bridges.cpp:110:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1;i<=m;i++) scanf("%d %d %d",&E[i].x,&E[i].y,&E[i].v);
                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:111:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int q;scanf("%d",&q);
        ~~~~~^~~~~~~~~
bridges.cpp:113:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&Q[qn].v,&Q[qn].x,&Q[qn].y);qn++;
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...