Submission #909192

#TimeUsernameProblemLanguageResultExecution timeMemory
909192089487Regions (IOI09_regions)C++14
100 / 100
1732 ms93236 KiB
#include<bits/stdc++.h> //#define int long long #define quick ios::sync_with_stdio(0);cin.tie(0); #define rep(x,a,b) for(int x=a;x<=b;x++) #define repd(x,a,b) for(int x=a;x>=b;x--) #define lowbit(x) (x&-x) #define F first #define S second #define sz(x) (int)(x.size()) #define all(x) x.begin(),x.end() #define mp make_pair #define eb emplace_back using namespace std; typedef pair<int,int> pii; void debug(){ cout<<"\n"; } template <class T,class ... U > void debug(T a, U ... b){ cout<<a<<" ",debug(b...); } const int N=2e5+2; const int M=25e3+7; const int K=600; const int K2=400; vector<int> cnt[M]; vector<int> inc[M]; vector<int> outc[M]; int pnt[K2][N]; int chd[K2][N]; int idx[N]; int c[N]; vector<int> v[N]; int in[N],out[N]; int t=1; void dfs(int x){ inc[c[x]].eb(t); in[x]=t++; for(int i:v[x]){ dfs(i); } outc[c[x]].eb(t); out[x]=t++; } void solve(int col,int _id,int x=1){ if(c[x]==col){ pnt[_id][x]+=1; chd[_id][x]+=1; } for(int i:v[x]){ chd[_id][i]+=chd[_id][x]; solve(col,_id,i); pnt[_id][x]+=pnt[_id][i]; } } long long bruforce(int c1,int c2){ int l=0; long long ans=0; for(int k:outc[c1]){ while(l<sz(inc[c2])&&inc[c2][l]<k){ l++; } ans+=l; } l=0; for(int k:inc[c1]){ while(l<sz(inc[c2])&&inc[c2][l]<k){ l++; } ans-=l; } return ans; } long long cntchild(int Id,int r1){ long long ans=0; for(int j:cnt[r1]){ ans+=chd[Id][j]; } return ans; } long long cntpnt(int Id,int r2){ long long ans=0; for(int j:cnt[r2]){ ans+=pnt[Id][j]; } return ans; } signed main(){ quick int n,r,q; cin>>n>>r>>q; cin>>c[1]; cnt[c[1]].eb(1); rep(i,2,n){ int p; cin>>p>>c[i]; cnt[c[i]].eb(i); v[p].eb(i); } dfs(1); int ID=0; rep(i,1,r){ if(sz(cnt[i])>=K){ idx[i]=ID++; solve(i,ID); idx[i]=ID; ID+=1; } } while(q--){ int r1,r2; cin>>r1>>r2; if(sz(cnt[r1])<K&&sz(cnt[r2])<K){ cout<<bruforce(r1,r2)<<endl; } else if(sz(cnt[r1])>sz(cnt[r2])){ cout<<cntchild(idx[r1],r2)<<endl; } else cout<<cntpnt(idx[r2],r1)<<endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...