제출 #1018750

#제출 시각아이디문제언어결과실행 시간메모리
1018750Denkata다리 (APIO19_bridges)C++17
59 / 100
3027 ms11444 KiB
#include<bits/stdc++.h> #define endl '\n' using namespace std; const int crit = 450; const int maxn = 1e5+3; int i,j,p,q,n,m,k,Q,br,d,ans[maxn+3]; int used[maxn]; struct Query { int type; int first,second; int ind; }; struct Edge { int u,v,d; }; vector <pair<int,int>> changed; vector <Edge> v; vector <Query> a,b; bool fff(Query a,Query b) { if(a.second!=b.second) return a.second>b.second; return a.type>b.type; } int par[maxn],sz[maxn]; int Find(int p) { if(par[p]==p) return p; return Find(par[p]); } stack <int> st,st2; void Union(int p,int q,bool fl) { p = Find(p); q = Find(q); // cout<<p<<" Union "<<q<<endl; if(p==q)return ; if(sz[p]>sz[q])swap(p,q); if(fl) st.push(p); par[p] = q; sz[q] += sz[p]; } void roll_back() { while(!st.empty()) { int t = st.top(); st.pop(); sz[par[t]]-=sz[t]; par[t] = t; } while(!st2.empty()) { p = st2.top(); st2.pop(); used[p] = 0; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>m; v.push_back({0,0,0});///parser for(i=1; i<=m; i++) { cin>>p>>q>>k; v.push_back({p,q,k}); } cin>>Q; for(i=1; i<=Q; i++) { cin>>p>>q>>k; b.push_back({p,q,k}); } for(int ii=0; ii<Q; ii+=crit) { //cout<<ii<<" query "<<endl; int R = min(ii+crit-1,Q-1); for(int jj=ii; jj<=R; jj++) a.push_back({b[jj].type,b[jj].first,b[jj].second,jj}); ++br; vector <Query> tek; changed.clear(); tek.clear(); for(auto i:a) { if(i.type==1) { p = i.first; q = i.second; // cout<<p<<" changed "<<endl; changed.push_back({p,i.ind}); used[p] = br; } else tek.push_back({-1,i.first,i.second,i.ind}); } for(i=1; i<=m; i++) { if(used[i]!=br) { // cout<<v[i].u<<" rebra "<<v[i].v<<" "<<v[i].d<<endl; tek.push_back({v[i].u,v[i].v,v[i].d}); } } sort(tek.begin(),tek.end(),fff); for(i=0; i<=n+1; i++) par[i] = i,sz[i] = 1; for(auto i:tek) { if(i.type!=-1) { p = i.type; q = i.first; // cout<<p<<" dobavqne "<<q<<endl; Union(p,q,0); } else { for(j=i.ind-1;j>=ii;j--) { if(b[j].type==1 && used[b[j].first]!=-1) { // cout<<"rebro predi query "<<b[j].first<<endl; used[b[j].first] = -1; st2.push(b[j].first); if(b[j].second>=i.second) Union(v[b[j].first].u,v[b[j].first].v,1); } } for(j=i.ind+1;j<=R;j++) { if(b[j].type==1 && used[b[j].first]!=-1) { // cout<<"rebro sled query "<<b[j].first<<endl; if(v[b[j].first].d>=i.second) Union(v[b[j].first].u,v[b[j].first].v,1); } } // cout<<i.first<<" "<<Find(i.first)<<" "<<sz[1]<<endl; ans[i.ind] = sz[Find(i.first)]; roll_back(); } } for(auto i:a) if(i.type==1)v[i.first].d = i.second; a.clear(); } for(i=0;i<Q;i++) { if(b[i].type==2) cout<<ans[i]<<endl; } return 0; } ///if an edge is updated more than once during the same bucket query processing! ///there is difference if an edge is updated before a query and after a query
#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...