Submission #725643

#	Time	Username	Problem	Language	Result	Execution time	Memory
725643		YENGOYAN	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	445 ms	41848 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 };

vector<int> ids;

struct func{
  bool operator()(const int a, const int b){
    return ids[a] < ids[b];
  }
};

void solve() {
  int n, q; cin >> n >> q;
  vector<int> par(n);
  vector<vector<int>> gp(n);
  vector<set<int>> to_check(n);
  ids = vector<int> (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);
  vector<int> order, sub(n);
  set<int, func> to_col;
    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];
    sub[u] = 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);
      sub[u] = min(sub[u], sub[v]);
    }
  };
  dfs(root);
  vector<vector<pair<int, int>>> new_gp(n);
  for(int i = 0; i < n; ++i){
    for(int &j : gp[i]){
      new_gp[i].push_back({sub[j], j});
    }
  }
  for(int i = 0; i < n; ++i){
    sort(new_gp[i].begin(), new_gp[i].end());
  }
  function<void(int)> get_order = [&](int u){
    for(pair<int, int> &v : new_gp[u]){
      get_order(v.second);
    }
    order.push_back(u);
  };
  get_order(root);
  for(int i = 0; i < n; ++i){
    ids[order[i]] = i;
  }
  function<int(int)> fnd = [&](int u){
    if(col[root]) {
      return root;
    }
    for(int i = 19; i >= 0; --i){
      if(col[up[u][i]]) {
        u = up[u][i];
      }
    }
    return u;
  };
  for(int i = 0; i < n; ++i) {
    if(gp[i].size() == 0 && i != root) {
      to_col.insert(i);
    }
  }
  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: 25 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5