oj.uz

Submission #131312

# Submission time Handle Problem Language Result Execution time Memory
131312 2019-07-17T03:57:57 Z dragonslayerit Regions (IOI09_regions) C++14
0 / 100
 1425 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);
  }
  
  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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6 ms 5496 KB Time limit exceeded (wall clock)
2 Execution timed out 2 ms 5544 KB Time limit exceeded (wall clock)
3 Execution timed out 6 ms 5624 KB Time limit exceeded (wall clock)
4 Execution timed out 6 ms 5624 KB Time limit exceeded (wall clock)
5 Execution timed out 8 ms 5752 KB Time limit exceeded (wall clock)
6 Execution timed out 16 ms 7032 KB Time limit exceeded (wall clock)
7 Execution timed out 11 ms 6136 KB Time limit exceeded (wall clock)
8 Execution timed out 21 ms 6904 KB Time limit exceeded (wall clock)
9 Execution timed out 66 ms 10104 KB Time limit exceeded (wall clock)
10 Execution timed out 70 ms 10232 KB Time limit exceeded (wall clock)
11 Execution timed out 192 ms 15864 KB Time limit exceeded (wall clock)
12 Execution timed out 266 ms 20216 KB Time limit exceeded (wall clock)
13 Execution timed out 49 ms 9336 KB Time limit exceeded (wall clock)
14 Execution timed out 287 ms 20344 KB Time limit exceeded (wall clock)
15 Execution timed out 498 ms 32888 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 845 ms 49764 KB Time limit exceeded (wall clock)
2 Execution timed out 1193 ms 61984 KB Time limit exceeded (wall clock)
3 Execution timed out 1020 ms 58076 KB Time limit exceeded (wall clock)
4 Execution timed out 433 ms 35112 KB Time limit exceeded (wall clock)
5 Execution timed out 521 ms 45560 KB Time limit exceeded (wall clock)
6 Execution timed out 734 ms 58236 KB Time limit exceeded (wall clock)
7 Execution timed out 1049 ms 81392 KB Time limit exceeded (wall clock)
8 Execution timed out 1425 ms 100980 KB Time limit exceeded (wall clock)
9 Runtime error 430 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 350 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 636 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 439 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 594 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 360 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 330 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 362 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)