Submission #253339

#	Time	Username	Problem	Language	Result	Execution time	Memory
253339		m3r8	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	394 ms	22264 KiB

ballmachine

#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 (stderr)

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 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5