Submission #1252024

#TimeUsernameProblemLanguageResultExecution timeMemory
1252024quocbaooBridges (APIO19_bridges)C++20
0 / 100
3094 ms4864 KiB
#include<bits/stdc++.h> #define fi first #define se second #define ll long long using namespace std; const int N=5e4; struct Node{ int fi,se,ba; }; stack<Node> st; int sz[N+5],par[N+5],u[N*2+5],v[N*2+5],w[N*2+5],t[N*2+5],kq[N*2+5]; int b[N*2+5],r[N*2+5],d[N*2+5],s[N*2+5],mp[N*2+5]; bool cmp(pair<int,int> u1,pair<int,int> v1){ return u1.fi>v1.fi; } int fd(int x){ if (x==par[x]) return x; int p=fd(par[x]); return par[x]=p; } void gop(int x,int y){ x=fd(x);y=fd(y); if (x==y) return; if (sz[x]<sz[y]) swap(x,y); sz[x]+=sz[y];par[y]=x; } int fd2(int x){ if (x==par[x]) return x; return fd(par[x]); } void gop2(int x,int y){ x=fd2(x);y=fd2(y); if (x==y) return; if (sz[x]<sz[y]) swap(x,y); st.push({x,sz[x],par[x]}); st.push({y,sz[y],par[y]}); sz[x]+=sz[y];par[y]=x; } int main(){ if (fopen("bridges.inp","r")){ freopen("bridges.inp","r",stdin); freopen("bridges.out","w",stdout); } ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); int n,m;cin>>n>>m; for (int i=1;i<=m;i++){ cin>>u[i]>>v[i]>>w[i]; } int q;cin>>q; for (int i=1;i<=q;i++){ cin>>t[i]; if (t[i]==1) cin>>b[i]>>r[i]; else cin>>s[i]>>d[i]; } int sq=int(sqrt(q));vector<int> v1;vector<pair<int,int>> v2,zz; for (int i=1;i<=q;i++){ v1.clear();v2.clear();zz.clear(); int j=min(i+sq,q); for (int i=1;i<=m;i++) mp[i]=0; for (int k=i;k<=j;k++){ if (t[k]==1) v1.push_back(k),mp[b[k]]++;else v2.push_back({d[k],k}); } sort(v2.begin(),v2.end(),cmp); for (int i=1;i<=m;i++){ if (mp[i]==0) zz.push_back({w[i],i}); } sort(zz.begin(),zz.end(),cmp); int bd=0; for (int i=1;i<=n;i++) sz[i]=1,par[i]=i; for (auto z:v2){ for (auto k:v1) mp[b[k]]=0; while (bd<zz.size()&&w[zz[bd].se]>=z.fi){ gop(u[zz[bd].se],v[zz[bd].se]); bd++; } for (int k=v1.size()-1;k>=0;k--){ if (mp[b[v1[k]]]==0&&v1[k]<z.se){ mp[b[v1[k]]]=1; if (r[v1[k]]>=z.fi) gop2(u[b[v1[k]]],v[b[v1[k]]]); } } for (int k=v1.size()-1;k>=0;k--){ if (mp[b[v1[k]]]==0){ mp[b[v1[k]]]=1; if (w[b[v1[k]]]>=z.fi) gop2(u[b[v1[k]]],v[b[v1[k]]]); } } kq[z.se]=sz[fd(s[z.se])]; while (!st.empty()){ int su=st.top().fi,kt=st.top().se,pa=st.top().ba; st.pop(); sz[su]=kt;par[su]=pa; } } for (int k=i;k<=j;k++){ if (t[k]==1) w[b[k]]=r[k]; } i=j; } // sort cau giam dan cau>=xe for (int i=1;i<=q;i++) if (t[i]==2) cout<<kq[i]<<'\n'; }

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen("bridges.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         freopen("bridges.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#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...