oj.uz

답안 #834340

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
834340 2023-08-22T13:15:52 Z andecaandeci Ball Machine (BOI13_ballmachine) C++17
4.84127 / 100
 134 ms 28144 KB 
#include <bits/stdc++.h>
#define inf INT_MAX
#define longlonginf LONG_LONG_MAX
#define mod  998244353
#define MAXN 100005
#define pii pair<ll,ll>
#define ll long long
#define deb(x) cerr<<"[ "<<#x<<" = "<<x<<" ]";
#define yes() cout<<"YES\n";
#define no() cout<<"NO\n";
using namespace std;

ll n,m,cur,q,x;
ll h;
ll ans = 0;
string subtask;
ll t;
ll par[MAXN][20];
vector<vector<ll>> child(MAXN);
ll root;
ll v[4*MAXN];
ll k;
bool vis[4*MAXN];

void build(ll x){
  if(child[x].size() == 0 ){
    v[x] = x;
    return;
  }
  for(int i = 0 ; i < (int) child[x].size() ; i++){
    build(child[x][i]);
  }
  v[x] = x;
  for(int i = 0 ; i < (int) child[x].size() ; i++){
    v[x] = min(v[x],child[x][i]);
  }
}

bool by_v(int a,int b){
  return v[a] < v[b];
}

void add(ll x){
  if( k == 0 ) return;
  //cout<<k<<" "<<"traversing ; "<<x<<"\n";
  if( child[x].size() == 0 ) {
    //cout<<"visiting : "<<x<<"\n";
    k--;
    vis[x] = 1;
    ans = x;
    return;
  }
  int cnt = 0;
  for(int i = 0 ; i < (int) child[x].size() ; i++){
    if( vis[child[x][i]] == 0 ){
      add(child[x][i]);
    }
    else cnt++;
  }
  //cout<<"visiting : "<<x<<"\n";
  k--;
  vis[x] = 1;
  ans = x;
  return;
}

void remove(int x,ll d){
  ll l = 0,r = n;
  ll u;
  ll tu;
  while( l <= r ){
    ll m = (l+r)/2;
    u = x;
    for(int i = 0; i <= 18 ; i++){
      if( ((1<<i) & m) != 0 ) u = par[u][i]; 
    }
    //cout<<"! "<<m<<" "<<u<<"\n";
    if( vis[u] == 0 ){
      tu = m;
      r = m-1;
    }
    else{
      l = m+1;
    }
  }
  tu--;
  //deb(tu);
  u = x;
  for(int i = 0; i <= 18 ; i++){
    if( ((1<<i) & tu) != 0 ) u = par[u][i]; 
  }
  //cout<<u<<"!\n";
  vis[u] = 0;
  cout<<tu<<"\n";
}

void solve(){
  cin>>n>>q;
  for(int i = 1 ; i <= n ; i++){
    cin>>x;
    if( x == 0 ) root = i;
    par[i][0] = x;
    child[x].push_back(i);
  }
  //init
  build(root);
  for(int i = 0 ; i <= n ; i++) par[root][i] = 0;
  for(int i = 1 ; i <= n ; i++) sort(child[i].begin(),child[i].end(),by_v);
  for(int i = 1 ; i <= 18 ; i++){
    for(int j = 1 ; j <= n ; j++){
      par[j][i] = par[par[j][i-1]][i-1];
    }
  }
  memset(vis,0,sizeof(vis));
  //queries
  while(q--){
    cin>>x;
    if( x == 1 ){
      cin>>k;
      add(1);
      cout<<ans<<"\n";
    }
    else{
      cin>>k;
      remove(k,0);
    }
  }
}


int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int T = 1;
  //cin>>T;
  for(int i = 0 ; i < T ; i++){
    //cout<<"Case #"<<i+1<<": ";
    solve();
  }
  return 0;
}

/*
  you thought u declared it huh?
  not i but x
  logical operator
  wrong example/proof
  thoroughly
  wrong variables
  thinking it wrong
  bruh just try some test case
  capitals ;-;
  wrong data structure lol
  count memory usement
  corner case
  oversized array
  orders
  statements
  size initializer
  while con
  map -> array
  wrong digits??
  swapped variables??
  check if theres any variabled
  that got declared twice
  find some pattern
  name collision
  constraints??!
  mod !!
  resets
*/

Compilation message

ballmachine.cpp: In function 'void remove(int, long long int)':
ballmachine.cpp:86:5: warning: 'tu' may be used uninitialized in this function [-Wmaybe-uninitialized]
   86 |   tu--;
      |   ~~^~

Subtask #1
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 3080 KB Output isn't correct
2 Incorrect 83 ms 15148 KB Output isn't correct
3 Incorrect 57 ms 14984 KB Output isn't correct
4 Incorrect 1 ms 3028 KB Output isn't correct
5 Incorrect 2 ms 3028 KB Output isn't correct
6 Incorrect 2 ms 3156 KB Output isn't correct
7 Incorrect 3 ms 3284 KB Output isn't correct
8 Incorrect 2 ms 3284 KB Output isn't correct
9 Incorrect 6 ms 3796 KB Output isn't correct
10 Incorrect 16 ms 6052 KB Output isn't correct
11 Incorrect 82 ms 15120 KB Output isn't correct
12 Incorrect 52 ms 14960 KB Output isn't correct
13 Incorrect 76 ms 15068 KB Output isn't correct

Subtask #2
4.28571428571 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 29 ms 7764 KB Output isn't correct
2 Incorrect 129 ms 24956 KB Output isn't correct
3 Correct 65 ms 21140 KB Output is correct
4 Incorrect 46 ms 9676 KB Output isn't correct
5 Incorrect 50 ms 9440 KB Output isn't correct
6 Incorrect 48 ms 9476 KB Output isn't correct
7 Incorrect 49 ms 8716 KB Output isn't correct
8 Incorrect 30 ms 7860 KB Output isn't correct
9 Incorrect 107 ms 25124 KB Output isn't correct
10 Incorrect 108 ms 24768 KB Output isn't correct
11 Incorrect 86 ms 24192 KB Output isn't correct
12 Incorrect 103 ms 22584 KB Output isn't correct
13 Incorrect 70 ms 24988 KB Output isn't correct
14 Correct 68 ms 21180 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 45 ms 14012 KB Output isn't correct
2 Incorrect 126 ms 23528 KB Output isn't correct
3 Incorrect 74 ms 22844 KB Output isn't correct
4 Incorrect 65 ms 20236 KB Output isn't correct
5 Incorrect 81 ms 19920 KB Output isn't correct
6 Incorrect 72 ms 19944 KB Output isn't correct
7 Incorrect 75 ms 19240 KB Output isn't correct
8 Incorrect 73 ms 22860 KB Output isn't correct
9 Incorrect 108 ms 24600 KB Output isn't correct
10 Incorrect 132 ms 24204 KB Output isn't correct
11 Incorrect 121 ms 24780 KB Output isn't correct
12 Incorrect 134 ms 23568 KB Output isn't correct
13 Incorrect 125 ms 28144 KB Output isn't correct
14 Incorrect 103 ms 21368 KB Output isn't correct

Subtask #4
0.555555555556 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 100 ms 24552 KB Output isn't correct
2 Incorrect 127 ms 23556 KB Output isn't correct
3 Incorrect 80 ms 27880 KB Output isn't correct
4 Incorrect 104 ms 24640 KB Output isn't correct
5 Incorrect 106 ms 24196 KB Output isn't correct
6 Incorrect 86 ms 24780 KB Output isn't correct
7 Incorrect 132 ms 23676 KB Output isn't correct
8 Incorrect 76 ms 27880 KB Output isn't correct
9 Correct 63 ms 21252 KB Output is correct