Submission #725371

#	Time	Username	Problem	Language	Result	Execution time	Memory
725371		YENGOYAN	Ball Machine (BOI13_ballmachine)	C++17	20.95 / 100	335 ms	36196 KiB

ballmachine

/*
                                    //\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\\
                                    \\                                    //
                                    //  271828___182845__904523__53602__  \\
                                    \\  87___47____13______52____66__24_  //
                                    //  97___75____72______47____09___36  \\
                                    \\  999595_____74______96____69___67  //
                                    //  62___77____24______07____66__30_  \\
                                    \\  35___35____47______59____45713__  //
                                    //                                    \\
                                    \\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\//
*/
#include <algorithm>
#include <bitset>
#include <chrono>
#include <climits>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
using LL = long long;
const int N = 1e5 + 5;
const LL mod = 1e9 + 7, inf = 1e18;

vector<int> dx = { 1, 0, 0, -1, 1, 1, -1, -1 };
vector<int> dy = { 0, 1, -1, 0, 1, -1, 1, -1 };

void solve() {
  int n, q; cin >> n >> q;
  vector<int> par(n);
  vector<vector<int>> gp(n);
  vector<set<int>> to_check(n);
  int root = 0;
  for(int i = 0; i < n ;++i){
    int p; cin >> p; --p;
    par[i] = p;
    if(p != -1) {
      gp[p].push_back(i);
      to_check[p].insert(i);
    }
    else root = i;
  }
  vector<int> col(n);
  set<int> to_col;
  for(int i = 0; i < n; ++i) {
    if(gp[i].size() == 0 && i != root) {
      to_col.insert(i);
    }
  }
  vector<vector<int>> up(n, vector<int> (20));
  vector<int> d(n);
  function<void(int)> dfs = [&](int u){
    if(par[u] == -1) up[u][0] = u;
    else up[u][0] = par[u];
    for(int i = 1; i < 20; ++i){
      up[u][i] = up[up[u][i - 1]][i - 1];
    }
    for(int &v : gp[u]){
      d[v] = d[u] + 1;
      dfs(v);
    }
  };
  dfs(root);
  function<int(int)> fnd = [&](int u){
    int cnt = 0;
    if(col[root]) {
      return root;
    }
    for(int i = 19; i >= 0; --i){
      if(col[up[u][i]]) {
        cnt += (1 << i);
        u = up[u][i];
      }
    }
    return u;
  };
  while(q--){
    int tp; cin >> tp;
    if(tp == 1){
      int k, lst = 0; cin >> k;
      while(k-- && to_col.size()){
        int u = *to_col.begin();
        lst = u;
        col[u] = 1;
        to_col.erase(u);
        if(par[u] != -1){
          to_check[par[u]].erase(u);
          if(to_check[par[u]].size() == 0){
            to_col.insert(par[u]);
          }
        }
      }
      cout << ++lst << "\n";
    }
    else {
      int u; cin >> u; --u;
      int lst_black = fnd(u);
      cout << d[u] - d[lst_black] << "\n";
      col[lst_black] = 0;
      to_col.insert(lst_black);
      to_col.erase(par[lst_black]);
      if(par[lst_black] != -1) {
        to_check[par[lst_black]].insert(lst_black);
      }
    }
  }

}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  // int t; cin >> t; while(t--)
  solve();
}

• Subtask 1: 0 / 25
• Subtask 2: 10.714285714285714 / 30
• Subtask 3: 8.571428571428571 / 40
• Subtask 4: 1.6666666666666667 / 5