Submission #131315

#	Time	Username	Problem	Language	Result	Execution time	Memory
131315		dragonslayerit	Regions (IOI09_regions)	C++14	55 / 100	2463 ms	131076 KiB

regions

#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>

int home[200005];
int ps[200005];
std::vector<int> children[200005];

int cut[200005];//cut from parent
int cut_cnt=0;
int height[200005];

void dfs_cut(int node){
  height[node]=1;
  for(int child:children[node]){
    dfs_cut(child);
    height[node]=std::max(height[node],height[child]+1);
  }
  if(height[node]>400||node==0){
    cut[node]=cut_cnt++;
    height[node]=0;
  }
}

int above[25000][500];
int below[25000][500];
std::vector<short> anc[25000];

int main(){
  int N,R,Q;
  scanf("%d %d %d",&N,&R,&Q);
  std::fill(cut,cut+N,-1);
  for(int i=0;i<N;i++){
    if(i){
      scanf("%d",&ps[i]);
      ps[i]--;
      children[ps[i]].push_back(i);
    }
    scanf("%d",&home[i]);
    home[i]--;
  }
  ps[0]=-1;
  dfs_cut(0);
  for(int i=0;i<N;i++){
    int x=i;
    while(cut[x]==-1){
      x=ps[x];
      anc[home[i]].push_back(home[x]);
    }
    below[home[i]][cut[x]]++;
  }
  for(int i=0;i<N;i++){
    if(cut[i]!=-1){
      for(int x=ps[i];x!=-1;x=ps[x]){
	above[home[x]][cut[i]]++;
      }
    }
  }
  /*
  for(int r=0;r<R;r++){
    printf("near[%d]: ",r);
    for(int x:anc[R]){
      printf("%d",x);
    }
    printf("\n");
  }
  for(int c=0;c<cut_cnt;c++){
    for(int r=0;r<R;r++){
      if(above[c][r]) printf("Above[%d]: %d x%d\n",c,r,above[c][r]);
    }
  }
  for(int c=0;c<cut_cnt;c++){
    for(int r=0;r<R;r++){
      if(below[c][r]) printf("Below[%d]: %d x%d\n",c,r,below[c][r]);
    }
  }
  */
  for(int i=0;i<R;i++){
    std::sort(anc[i].begin(),anc[i].end());
  }
  while(Q-->0){
    int R1,R2;
    scanf("%d %d",&R1,&R2);
    R1--,R2--;
    int ans=std::upper_bound(anc[R2].begin(),anc[R2].end(),R1)-
      std::lower_bound(anc[R2].begin(),anc[R2].end(),R1);
    /*
    for(int x:anc[R2]){
      if(x==R1) ans++;
    }
    */
    for(int c=0;c<cut_cnt;c++){
      ans+=above[R1][c]*below[R2][c];
    }
    printf("%d\n",ans);
    fflush(stdout);
  }
  
  return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&N,&R,&Q);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:36:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d",&ps[i]);
       ~~~~~^~~~~~~~~~~~~
regions.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&home[i]);
     ~~~~~^~~~~~~~~~~~~~~
regions.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&R1,&R2);
     ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 40 / 85