제출 #1314129

#제출 시각아이디문제언어결과실행 시간메모리
1314129boclobanchat동기화 (JOI13_synchronization)C++20
100 / 100
5876 ms113116 KiB
#include<bits/stdc++.h> using namespace std; const int MAXN=1e5+5; const int N=6767; bitset<N> bt[MAXN]; vector<int> vi[MAXN*8]; pair<int,int> edge[MAXN]; int pos[MAXN],ans[MAXN],dsu[MAXN],cnt[MAXN]; stack< pair<int,int> > st; int root(int i) { if(!dsu[i]) return i; return root(dsu[i]); } void merge(int i,int j,int p) { i=root(i),j=root(j); if(cnt[i]<cnt[j]) swap(i,j); dsu[j]=i,cnt[i]+=cnt[j],bt[i]|=bt[j]; st.push({i,j}); } void rollback() { int l=st.top().first,r=st.top().second; st.pop(); dsu[r]=0,cnt[l]-=cnt[r],bt[r]=bt[l]; } void update(int l,int r,int u,int v,int val,int pos) { if(v<l||r<u) return ; if(u<=l&&r<=v) { vi[pos].push_back(val); return ; } int mid=(l+r)/2; update(l,mid,u,v,val,pos*2); update(mid+1,r,u,v,val,pos*2+1); } void dnc(int l,int r,int pos) { for(auto v:vi[pos]) merge(edge[v].first,edge[v].second,v); if(l!=r) { int mid=(l+r)/2; dnc(l,mid,pos*2); dnc(mid+1,r,pos*2+1); } for(auto v:vi[pos]) rollback(); } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,m,q; cin>>n>>m>>q; for(int i=1;i<n;i++) cin>>edge[i].first>>edge[i].second; for(int i=1;i<=m;i++) { int res; cin>>res; if(!pos[res]) pos[res]=i; else { update(1,m,pos[res],i-1,res,1); pos[res]=0; } } for(int i=1;i<n;i++) if(pos[i]) update(1,m,pos[i],m,i,1); int pre=1; for(int i=1;i<=n;i++) cnt[i]=1; for(int i=1;i<=n;i++) if(i%N==0||i==n) { for(int j=pre;j<=i;j++) bt[j][(j-1)%N]=1; pre=i+1; dnc(1,m,1); for(int j=1;j<=n;j++) ans[j]+=bt[j].count(),bt[j]=0; } while(q--) { int res; cin>>res; cout<<ans[res]<<"\n"; } }
#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...