| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 895332 | ilef | Regions (IOI09_regions) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+12;
const int R=1001;
int H[N];
vector<int>graph[N];
vector<int>v[R];
int id[N];
int sz[R][N];
int trav[R][N];
void dfs(int u,int r2,int p,int &cnt){
id[u]=cnt;
sz[r2][u]=1;
if(H[u]==r2){
trav[r2][cnt]=1;
}
else{
trav[r2][cnt]=0;
}
cnt++;
for(auto v:graph[u]){
if(v!=p){
dfs(v,r2,u,cnt);
sz[r2][u]+=sz[r2][v];
}
}
}
struct segtree{
int size;
vector<vector<int>>sums;
void init(int n){
size=1;
while(size<n){
size*=2;
}
sums.assign(R,vector<int>(2*size,0LL));
}
void build(vector<vector<int>>&a,int x,int lx,int rx,int r){
if(rx-lx==1){
if(lx<(int)a[r].size()){
sums[r][x]=a[r][lx];
}
return ;
}
int m=(lx+rx)/2;
build(a,2*x+1,lx,m,r);
build(a,2*x+2,m,rx,r);
sums[r][x]=sums[r][2*x+1]+sums[r][2*x+2];
}
void build(vector<vector<int>>&a,int r){
build(a,0,0,size,r);
}
void set(int i,int v,int x,int lx,int rx,int r){
if(rx-lx==1){
sums[r][x]=v;
return ;
}
int m=(lx+rx)/2;
if(i<m){
set(i,v,2*x+1,lx,m,r);
}
else{
set(i,v,2*x+2,m,rx,r);
}
sums[r][x]=sums[r][2*x+1]+sums[r][2*x+2];
}
void set(int i,int v,int r){
set(i,v,0,0,size, r);
}
long long sum(int l,int r,int x,int lx,int rx,int rr){
if(lx>=r || l>=rx){
return 0;
}
if(lx>=l && rx<=r){
return sums[rr][x];
}
int m=(lx+rx)/2;
return sum(l,r,2*x+1,lx,m,rr)+sum(l,r,2*x+2,m,rx,rr);
}
long long sum(int l,int r,int rr){
return sum(l,r,0,0,size,rr);
}
};
int32_t main(){
int n,r,q;
cin>>n>>r>>q;
cin>>H[0];
H[0]--;
v[H[0]].push_back(0);
for(int i=1;i<=n-1;i++){
//cout<<1<<endl;
int u;
cin>>u>>H[i];
H[i]--;
u--;
v[H[i]].push_back(i);
graph[u].push_back(i);
graph[i].push_back(u);
}
for(int j=0;j<r;j++){
//cout<<1<<endl;
int cnt=0;
dfs(0,j,-1,cnt);
}
vector<vector<int>>val(r,vector<int>(n,0LL));
for(int i=0;i<n;i++){
for(int j=0;j<r;j++){
val[j][i]=trav[j][i];
}
}
segtree st;
st.init(n);
for(int j=0;j<r;j++){
//cout<<1<<endl;
st.build(val,j);}
while(q--){
//cout<<1<<endl;
int r1,r2;
cin>>r1>>r2;
//cout<<endl;
r1--;r2--;
int summ=0;
for(auto u:v[r1]){
int a=id[u];
int szz=sz[r2][u];
//cout<<szz<<endl;
summ+=st.sum(a,a+szz,r2);
if(r1==r2){
summ--;
}
}
cout<<summ<<endl;
}
}