oj.uz

Submission #131315

# Submission time Handle Problem Language Result Execution time Memory
131315 2019-07-17T04:02:12 Z dragonslayerit Regions (IOI09_regions) C++14
55 / 100
 2463 ms 131076 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5496 KB Output is correct
2 Correct 6 ms 5624 KB Output is correct
3 Correct 9 ms 5624 KB Output is correct
4 Correct 11 ms 5752 KB Output is correct
5 Correct 12 ms 5752 KB Output is correct
6 Correct 36 ms 7160 KB Output is correct
7 Correct 30 ms 6264 KB Output is correct
8 Correct 54 ms 6944 KB Output is correct
9 Correct 91 ms 10176 KB Output is correct
10 Correct 158 ms 10228 KB Output is correct
11 Correct 302 ms 15880 KB Output is correct
12 Correct 401 ms 20216 KB Output is correct
13 Correct 188 ms 9424 KB Output is correct
14 Correct 456 ms 20224 KB Output is correct
15 Correct 700 ms 32976 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1606 ms 49824 KB Output is correct
2 Correct 2094 ms 61992 KB Output is correct
3 Correct 2416 ms 58224 KB Output is correct
4 Correct 653 ms 35188 KB Output is correct
5 Correct 871 ms 45676 KB Output is correct
6 Correct 1357 ms 58400 KB Output is correct
7 Correct 1719 ms 81440 KB Output is correct
8 Correct 2463 ms 101012 KB Output is correct
9 Runtime error 433 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 358 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 438 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 670 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 431 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 569 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 367 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 331 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 361 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)