| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 725642 | YENGOYAN | Ball Machine (BOI13_ballmachine) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
//\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\\
\\ //
// 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();
}