oj.uz

Submission #253339

# Submission time Handle Problem Language Result Execution time Memory
253339 2020-07-27T18:32:03 Z m3r8 Ball Machine (BOI13_ballmachine) C++14
100 / 100
 394 ms 22264 KB 
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <functional>
#include <utility>

#define N 100100
#define left(i) (i<<1)
#define right(i) ((i<<1)+1)
#define ii std::pair<int,int>

typedef struct trr{
  int sum;
  int lz;
}trr;

trr seg[N*4];

void prop(int idx, int l, int r){
  if(seg[idx].lz){
    if(l != r-1){
      int md = (l+r)>>1;
      seg[left(idx)].lz = seg[right(idx)].lz = 1;  
      seg[left(idx)].sum = md-l;
      seg[right(idx)].sum = r-md;
      seg[idx].sum = seg[left(idx)].sum + seg[right(idx)].sum;
    };
    seg[idx].lz = 0;
  };  
};

int up1(int idx, int l, int r, int k){
  prop(idx,l,r);
  if(l == r-1){
    seg[idx].sum = 1;  
    return l;
  }else{
    int md = (l+r)>>1;
    int r1 = md-l;
    int r2 = r-md;
    int erg;
    if(r1 - seg[left(idx)].sum >= k){
      erg = up1(left(idx),l,md,k);  
    }else{
      int tmp = seg[left(idx)].sum;
      seg[left(idx)].lz = 1;
      seg[left(idx)].sum = r1;
      erg = up1(right(idx),md,r,k-r1+tmp);  
    };
    seg[idx].sum = seg[left(idx)].sum + seg[right(idx)].sum;
    return erg;
  };
};

void up2(int idx, int l, int r, int x){
  prop(idx,l,r);
  if(l == r-1){
    seg[idx].sum = 0;
  }else{
    int md = (l+r)>>1;
    if(x < md){
      up2(left(idx),l,md,x);  
    }else{
      up2(right(idx),md,r,x);  
    };
    seg[idx].sum = seg[left(idx)].sum + seg[right(idx)].sum;
  };  
};

int qry(int idx, int l, int r, int x){
  prop(idx,l,r);  
  if(l == r-1){
    return seg[idx].sum;
  }else{
    int md = (l+r)>>1;  
    if(x < md){
      return qry(left(idx),l,md,x);  
    }else{
      return qry(right(idx),md,r,x);  
    };
  };
};

int in[N];
int mp[N];
int cnt = 0;
int par[N][20];
int ptz[20];
int mn[N];

std::vector<ii> adj[N];

void dfs1(int v, int p){
  mn[v] = v;
  for(int i = 0;i<adj[v].size();i++){
    ii akt = adj[v][i];
    dfs1(akt.second,v);
    mn[v] = std::min(mn[v],mn[akt.second]);
    adj[v][i].first = mn[akt.second];
  };
};

void dfs(int v, int p){
  par[v][0] = p;  
  for(int i = 1;i<20;i++){
    par[v][i] = par[par[v][i-1]][i-1];   
  };
  for(auto i: adj[v]){
    if(!in[i.second]){
      dfs(i.second,v);
    };  
  };
  in[v] = cnt++;
  mp[in[v]] = v;
};
int n;  

int ib(int idx){
  if(idx == 0)return 0;  
  else return qry(1,0,n,in[idx]);
};

int main(void){
  ptz[0] = 1;
  for(int i = 1;i<20;i++){
    ptz[i] = ptz[i-1] * 2;
  };
  int q;
  scanf("%d %d",&n,&q);
  int pp;
  int rr;
  for(int i = 1;i<=n;i++){
    scanf("%d",&pp);
    if(pp){
      adj[pp].push_back({0,i});  
    }else{
      rr = i;  
    };
  };
  dfs1(rr,0);
  for(int i = 1;i<=n;i++){
    std::sort(adj[i].begin(),adj[i].end(),std::less<ii>());  
  };
  dfs(rr,0);
  int k;
  for(int i = 0;i<q;i++){
    scanf("%d %d",&k,&pp);
    if(k == 1){
      printf("%d\n",mp[up1(1,0,n,pp)]);  
    }else{
      int akt = pp;
      int erg = 0;
      for(int i = 19;i>=0;i--){
        if(ib(par[akt][i])){
          erg += ptz[i];
          akt = par[akt][i];
        };  
      };
      up2(1,0,n,in[akt]);
      printf("%d\n",erg);
    };
  };
  return 0;
};

Compilation message

ballmachine.cpp: In function 'int up1(int, int, int, int)':
ballmachine.cpp:40:9: warning: unused variable 'r2' [-Wunused-variable]
     int r2 = r-md;
         ^~
ballmachine.cpp: In function 'void dfs1(int, int)':
ballmachine.cpp:95:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0;i<adj[v].size();i++){
                 ~^~~~~~~~~~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:129:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&n,&q);
   ~~~~~^~~~~~~~~~~~~~~
ballmachine.cpp:133:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&pp);
     ~~~~~^~~~~~~~~~
ballmachine.cpp:147:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&k,&pp);
     ~~~~~^~~~~~~~~~~~~~~~
ballmachine.cpp:144:6: warning: 'rr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   dfs(rr,0);
   ~~~^~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2816 KB Output is correct
2 Correct 132 ms 10744 KB Output is correct
3 Correct 86 ms 10104 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2816 KB Output is correct
7 Correct 3 ms 2816 KB Output is correct
8 Correct 3 ms 2816 KB Output is correct
9 Correct 9 ms 3200 KB Output is correct
10 Correct 25 ms 4736 KB Output is correct
11 Correct 142 ms 10748 KB Output is correct
12 Correct 85 ms 10104 KB Output is correct
13 Correct 114 ms 9976 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 6136 KB Output is correct
2 Correct 287 ms 17912 KB Output is correct
3 Correct 95 ms 13548 KB Output is correct
4 Correct 110 ms 7544 KB Output is correct
5 Correct 147 ms 7544 KB Output is correct
6 Correct 145 ms 7160 KB Output is correct
7 Correct 134 ms 6776 KB Output is correct
8 Correct 59 ms 6136 KB Output is correct
9 Correct 280 ms 17988 KB Output is correct
10 Correct 304 ms 17784 KB Output is correct
11 Correct 263 ms 16504 KB Output is correct
12 Correct 270 ms 15992 KB Output is correct
13 Correct 140 ms 18040 KB Output is correct
14 Correct 106 ms 13548 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 10872 KB Output is correct
2 Correct 347 ms 17528 KB Output is correct
3 Correct 200 ms 18160 KB Output is correct
4 Correct 181 ms 15608 KB Output is correct
5 Correct 214 ms 15352 KB Output is correct
6 Correct 210 ms 15352 KB Output is correct
7 Correct 236 ms 14456 KB Output is correct
8 Correct 241 ms 18168 KB Output is correct
9 Correct 286 ms 19068 KB Output is correct
10 Correct 393 ms 18680 KB Output is correct
11 Correct 364 ms 18680 KB Output is correct
12 Correct 366 ms 17400 KB Output is correct
13 Correct 394 ms 22264 KB Output is correct
14 Correct 145 ms 15596 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 18296 KB Output is correct
2 Correct 297 ms 17144 KB Output is correct
3 Correct 155 ms 20088 KB Output is correct
4 Correct 259 ms 18296 KB Output is correct
5 Correct 311 ms 17784 KB Output is correct
6 Correct 270 ms 16608 KB Output is correct
7 Correct 298 ms 16888 KB Output is correct
8 Correct 155 ms 20088 KB Output is correct
9 Correct 90 ms 13552 KB Output is correct