oj.uz

답안 #881310

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
881310 2023-12-01T05:16:17 Z noompty Ball Machine (BOI13_ballmachine) C++17
100 / 100
 95 ms 29632 KB 
#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <map>
#include <cmath>
#include <array>
#include <random>
#include <string>
#include <cassert>
#include <climits>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
using namespace std;
 
#define ll long long
#define f first
#define s second
 
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
 
template<typename A> void __print(const A &x);
template<typename A, typename B> void __print(const pair<A, B> &p);
template<typename... A> void __print(const tuple<A...> &t);
template<typename T> void __print(stack<T> s);
template<typename T> void __print(queue<T> q);
template<typename T, typename... U> void __print(priority_queue<T, U...> q);
 
template<typename A> void __print(const A &x) {
    bool first = true;
    cerr << '{';
    for (const auto &i : x) {
        cerr << (first ? "" : ","), __print(i);
        first = false;
    }
    cerr << '}';
}
 
template<typename A, typename B> void __print(const pair<A, B> &p) {
    cerr << '(';
    __print(p.f);
    cerr << ',';
    __print(p.s);
    cerr << ')';
}
 
template<typename... A> void __print(const tuple<A...> &t) {
    bool first = true;
    cerr << '(';
    apply([&first] (const auto &...args) { ((cerr << (first ? "" : ","), __print(args), first = false), ...); }, t);
    cerr << ')';
}
 
template<typename T> void __print(stack<T> s) {
    vector<T> debugVector;
    while (!s.empty()) {
        T t = s.top();
        debugVector.push_back(t);
        s.pop();
    }
    reverse(debugVector.begin(), debugVector.end());
    __print(debugVector);
}
 
template<typename T> void __print(queue<T> q) {
    vector<T> debugVector;
    while (!q.empty()) {
        T t = q.front();
        debugVector.push_back(t);
        q.pop();
    }
    __print(debugVector);
}
 
template<typename T, typename... U> void __print(priority_queue<T, U...> q) {
    vector<T> debugVector;
    while (!q.empty()) {
        T t = q.top();
        debugVector.push_back(t);
        q.pop();
    }
    __print(debugVector);
}
 
void _print() { cerr << "]\n"; }
 
template <typename Head, typename... Tail> void _print(const Head &H, const Tail &...T) {
    __print(H);
    if (sizeof...(T)) cerr << ", ";
    _print(T...);
}
 
#ifdef DEBUG
	#define D(...) cerr << "Line: " << __LINE__ << " [" << #__VA_ARGS__ << "] = ["; _print(__VA_ARGS__)
#else
	#define D(...)
#endif

int n, q, rt, mn[100005], out[100005], idx, par[100005][20], k, v, ans, depth[100005], tmp;
bool filled[100005];
vector<int> adj[100005];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

void dfs1(int curr) {
    mn[curr] = curr;
    for (int i : adj[curr]) {
        depth[i] = depth[curr] + 1;
        dfs1(i);
        mn[curr] = min(mn[curr], mn[i]);
    }
}

void dfs2(int curr) {
    vector<pair<int, int>> ord;
    for (int i : adj[curr]) {
        ord.push_back({mn[i], i});
    }
    sort(ord.begin(), ord.end());
    for (auto [m, x] : ord) {
        dfs2(x);
    }
    out[curr] = idx++;
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> par[i][0];
        if (!par[i][0]) {
            rt = i;
            continue;
        }
        adj[par[i][0]].push_back(i);
    }

    dfs1(rt);
    dfs2(rt);

    for (int i = 1; i <= n; i++) {
        // cout << i << ": " << out[i] << " " << depth[i] << "\n";
        pq.push({out[i], i});
    }

    for (int i = 1; i < 20; i++) {
        for (int j = 1; j <= n; j++) {
            par[j][i] = par[par[j][i - 1]][i - 1];
        }
    }

    while (q--) {
        cin >> k >> v;
        if (k == 1) {
            while (v--) {
                ans = pq.top().s;
                filled[ans] = true;
                pq.pop();
            }
            cout << ans << "\n";
        } else {
            tmp = v;
            for (int i = 19; i >= 0; i--) {
                if (filled[par[tmp][i]]) {
                    tmp = par[tmp][i];
                }
            }
            cout << depth[v] - depth[tmp] << "\n";
            filled[tmp] = false;
            pq.push({out[tmp], tmp});
        }
    }

}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 61 ms 11084 KB Output is correct
3 Correct 38 ms 11364 KB Output is correct
4 Correct 1 ms 4696 KB Output is correct
5 Correct 1 ms 4696 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct
9 Correct 5 ms 4700 KB Output is correct
10 Correct 13 ms 5412 KB Output is correct
11 Correct 58 ms 11116 KB Output is correct
12 Correct 38 ms 11212 KB Output is correct
13 Correct 54 ms 11212 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 8272 KB Output is correct
2 Correct 85 ms 21844 KB Output is correct
3 Correct 46 ms 14668 KB Output is correct
4 Correct 42 ms 10072 KB Output is correct
5 Correct 40 ms 10304 KB Output is correct
6 Correct 39 ms 10076 KB Output is correct
7 Correct 39 ms 8912 KB Output is correct
8 Correct 25 ms 8284 KB Output is correct
9 Correct 72 ms 22156 KB Output is correct
10 Correct 81 ms 21840 KB Output is correct
11 Correct 78 ms 21984 KB Output is correct
12 Correct 72 ms 18000 KB Output is correct
13 Correct 58 ms 26964 KB Output is correct
14 Correct 46 ms 14656 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 14420 KB Output is correct
2 Correct 81 ms 18508 KB Output is correct
3 Correct 62 ms 25608 KB Output is correct
4 Correct 53 ms 19796 KB Output is correct
5 Correct 57 ms 19472 KB Output is correct
6 Correct 62 ms 19644 KB Output is correct
7 Correct 61 ms 16988 KB Output is correct
8 Correct 63 ms 25420 KB Output is correct
9 Correct 86 ms 22328 KB Output is correct
10 Correct 79 ms 22096 KB Output is correct
11 Correct 82 ms 22096 KB Output is correct
12 Correct 76 ms 18468 KB Output is correct
13 Correct 93 ms 29632 KB Output is correct
14 Correct 65 ms 14568 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 22524 KB Output is correct
2 Correct 87 ms 18512 KB Output is correct
3 Correct 71 ms 29268 KB Output is correct
4 Correct 95 ms 22472 KB Output is correct
5 Correct 89 ms 22216 KB Output is correct
6 Correct 75 ms 22100 KB Output is correct
7 Correct 78 ms 18520 KB Output is correct
8 Correct 62 ms 29304 KB Output is correct
9 Correct 48 ms 14668 KB Output is correct