oj.uz

Submission #824243

# Submission time Handle Problem Language Result Execution time Memory
824243 2023-08-13T20:35:46 Z EthanKim8683 Regions (IOI09_regions) C++17
100 / 100
 4275 ms 60120 KB 
#include<bits/stdc++.h>
using namespace std;
using I=int;
using B=bool;
const I N=200000;
const I R=25000;
const I LOGN=18;
I h_arr[N];
vector<I>adjs[N];
map<pair<I,I>,I>ress;
I tbgs[N],teds[N];
vector<I>cits[R];
vector<I>tims[R];
vector<I>spas[R][LOGN];
I viss[R];
I cnts[N];
I t=0;
void dfs(I a,I dep=0){
  I h=h_arr[a];
  cits[h].push_back(a);
  viss[h]++,cnts[a]=viss[h];
  tbgs[a]=t++;
  for(auto b:adjs[a])dfs(b,dep+1);
  teds[a]=t;
  viss[h]--;
}
void bld(I i){
  for(I j=1;j<LOGN;j++)for(I k=0;k+(1<<j)<=cits[i].size();k++)spas[i][j].push_back(max(spas[i][j-1][k],spas[i][j-1][k+(1<<(j-1))]));
}
I qry(I i,I l,I r){
  I d=31-__builtin_clz(r-l);
  return max(spas[i][d][l],spas[i][d][r-(1<<d)]);
}
I slv1(I i,I j){
  return lower_bound(tims[j].begin(),tims[j].end(),teds[i])-lower_bound(tims[j].begin(),tims[j].end(),tbgs[i]);
}
I slv2(I i,I j){
  I k=upper_bound(tims[j].begin(),tims[j].end(),tbgs[i])-tims[j].begin()-1;
  if(k<0)return 0;
  I l=0,r=k;
  while(l<r){
    I m=l+(r-l+1)/2;
    qry(j,m,k+1)>=teds[i]?l=m:r=m-1;
  }
  return qry(j,l,k+1)>=teds[i]?cnts[cits[j][l]]:0;
}
I main(){
  cin.tie(0)->sync_with_stdio(0);
  I n,r,q;cin>>n>>r>>q;
  I h;cin>>h,h--;
  h_arr[0]=h;
  for(I i=1;i<n;i++){
    I s,h;cin>>s>>h,s--,h--;
    adjs[s].push_back(i);
    h_arr[i]=h;
  }
  dfs(0);
  for(I i=0;i<r;i++){
    for(auto j:cits[i])tims[i].push_back(tbgs[j]),spas[i][0].push_back(teds[j]);
    bld(i);
  }
  while(q--){
    I r1,r2;cin>>r1>>r2,r1--,r2--;
    auto it=ress.find({r1,r2});
    if(it!=ress.end()){
      printf("%i\n",it->second),fflush(stdout);
      continue;
    }
    I res=0;
    if(cits[r1].size()<cits[r2].size())for(auto i:cits[r1])res+=slv1(i,r2);
    if(cits[r2].size()<=cits[r1].size())for(auto i:cits[r2])res+=slv2(i,r1);
    ress[{r1,r2}]=res;
    printf("%i\n",res),fflush(stdout);
  }
}

Compilation message

regions.cpp: In function 'void bld(I)':
regions.cpp:28:42: warning: comparison of integer expressions of different signedness: 'I' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   for(I j=1;j<LOGN;j++)for(I k=0;k+(1<<j)<=cits[i].size();k++)spas[i][j].push_back(max(spas[i][j-1][k],spas[i][j-1][k+(1<<(j-1))]));
      |                                  ~~~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16672 KB Output is correct
2 Correct 8 ms 16788 KB Output is correct
3 Correct 10 ms 16800 KB Output is correct
4 Correct 13 ms 16808 KB Output is correct
5 Correct 16 ms 16860 KB Output is correct
6 Correct 26 ms 16976 KB Output is correct
7 Correct 27 ms 16936 KB Output is correct
8 Correct 41 ms 17088 KB Output is correct
9 Correct 59 ms 17748 KB Output is correct
10 Correct 71 ms 18124 KB Output is correct
11 Correct 128 ms 18632 KB Output is correct
12 Correct 120 ms 19528 KB Output is correct
13 Correct 144 ms 19568 KB Output is correct
14 Correct 251 ms 20372 KB Output is correct
15 Correct 257 ms 24124 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1131 ms 27000 KB Output is correct
2 Correct 1250 ms 26148 KB Output is correct
3 Correct 2001 ms 31800 KB Output is correct
4 Correct 195 ms 21152 KB Output is correct
5 Correct 338 ms 23668 KB Output is correct
6 Correct 394 ms 23484 KB Output is correct
7 Correct 586 ms 24276 KB Output is correct
8 Correct 909 ms 34620 KB Output is correct
9 Correct 1866 ms 40940 KB Output is correct
10 Correct 3510 ms 49508 KB Output is correct
11 Correct 4275 ms 45968 KB Output is correct
12 Correct 1509 ms 40444 KB Output is correct
13 Correct 2072 ms 43032 KB Output is correct
14 Correct 2224 ms 45036 KB Output is correct
15 Correct 2662 ms 52988 KB Output is correct
16 Correct 2804 ms 60120 KB Output is correct
17 Correct 3143 ms 58692 KB Output is correct