Submission #643484

#	Time	Username	Problem	Language	Result	Execution time	Memory
643484		christinelynn	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	166 ms	38544 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define db double
#define pairll pair<ll,ll>
#define lpairll pair<ll,pairll>

#define repp(i,a,b) for (ll i = a; i <= b; i++)
#define repz(i,a,b) for (ll i = a; i < b; i++)
#define repm(i,a,b) for (ll i = a; i >= b; i--)
#define fr first
#define sc second
#define mp make_pair
#define pb push_back

const ll N = 2e5+5, MOD = 1e9+7, LOG = 20;
ll tc = 1, n, m, ar[N], br[N], used[N];
ll x, y, k, cur = 0;
string s, s1, s2, ye = "YES", no = "NO";
ll ord[N], root, nx[N][LOG+5], dlm[N], smol[N];
vector<ll> ed[N];

void buildord(ll idx){
  for (auto i : ed[idx]){
    dlm[i] = dlm[idx]+1;
    buildord(i);
  }
  cur++;
  ord[idx] = cur;
}

void buildlift(){
  nx[root][0] = 0;
  repp(bt,1,LOG){
    repp(i,1,n){
      nx[i][bt] = nx[nx[i][bt-1]][bt-1];
    }
  }
}

void input(){
  cin >> n >> m;
  repp(i,1,n){
    cin >> ar[i];
    if (ar[i] == 0){
      if (root != 0) assert(0);
      root = i;
    }
    else{
      ed[ar[i]].pb(i);
      nx[i][0] = ar[i];
    }
  }
}

void buildsmol(ll idx){
  smol[idx] = idx;
  for (auto i : ed[idx]){
    buildsmol(i);
    smol[idx] = min(smol[idx],smol[i]);
  }
  //cout << idx << " " << smol[idx] << endl;
}

bool cmp (ll a, ll b){
  return (smol[a] < smol[b]);
}

void solve(){
  buildsmol(root);
  repp(i,1,n){
    sort(ed[i].begin(),ed[i].end(),cmp);
  }
  buildord(root);
  buildlift();
  priority_queue<pairll, vector<pairll>, greater<pairll> > pq;
  repp(i,1,n){
    pq.push(mp(ord[i],i));
  }
  while(m--){
    cin >> x >> y;
    if (x == 1){
      ll lst;
      while(y--){
        pairll a = pq.top();
        pq.pop();
        used[a.sc] = 1;
        lst = a.sc;
      }
      cout << lst << "\n";
    }
    else if(x == 2){
      ll dis = 0, ori = y;
      repm(bt,LOG,0){
        if (used[nx[y][bt]]){
          dis += (1<<bt);
          y = nx[y][bt];
        }
      }
      used[y] = 0;
      pq.push(mp(ord[y],y));
      cout << dis << "\n";
    }
  }
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  //cin >> tc;
  while(tc--){
    input();
    solve();
  }
}

Compilation message (stderr)

ballmachine.cpp: In function 'void solve()':
ballmachine.cpp:94:19: warning: unused variable 'ori' [-Wunused-variable]
   94 |       ll dis = 0, ori = y;
      |                   ^~~

• Subtask 1: 25 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5