oj.uz

답안 #781375

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
781375 2023-07-13T04:56:06 Z horiiseun Ball Machine (BOI13_ballmachine) C++17
100 / 100
 107 ms 23880 KB 
#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <map>
#include <cmath>
#include <random>
#include <string>
#include <bitset>
#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, par[100005][20], mn[100005], out[100005], idx, op, v, nd, ans, depth[100005];
vector<int> adj[100005];
bool filled[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) {
    for (int i : adj[curr]) {
        dfs2(i);
    }
    out[curr] = idx++;
}

int main() {

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

    cin >> n >> q;
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        par[i][0] = x;
        adj[x].push_back(i);    
    }

    dfs1(0);

    for (int i = 1; i <= 19; i++) {
        for (int j = 1; j <= n; j++) {
            par[j][i] = par[par[j][i - 1]][i - 1];
        }
    }    
    
    for (int i = 1; i <= n; i++) {
        sort(adj[i].begin(), adj[i].end(), [](int x, int y) {
            return mn[x] < mn[y];
        });
    }

    dfs2(0);
    
    for (int i = 1; i <= n; i++) {
        pq.push({out[i], i});
    }

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

}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2684 KB Output is correct
2 Correct 61 ms 11644 KB Output is correct
3 Correct 39 ms 11516 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2684 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2820 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 5 ms 3284 KB Output is correct
10 Correct 14 ms 4960 KB Output is correct
11 Correct 60 ms 11588 KB Output is correct
12 Correct 39 ms 11540 KB Output is correct
13 Correct 55 ms 11612 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 7072 KB Output is correct
2 Correct 81 ms 19192 KB Output is correct
3 Correct 46 ms 15168 KB Output is correct
4 Correct 40 ms 8272 KB Output is correct
5 Correct 45 ms 8196 KB Output is correct
6 Correct 39 ms 8204 KB Output is correct
7 Correct 40 ms 7328 KB Output is correct
8 Correct 24 ms 7040 KB Output is correct
9 Correct 79 ms 19652 KB Output is correct
10 Correct 82 ms 19300 KB Output is correct
11 Correct 72 ms 19300 KB Output is correct
12 Correct 89 ms 17436 KB Output is correct
13 Correct 55 ms 21196 KB Output is correct
14 Correct 47 ms 15176 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 11340 KB Output is correct
2 Correct 92 ms 17808 KB Output is correct
3 Correct 65 ms 19368 KB Output is correct
4 Correct 59 ms 16252 KB Output is correct
5 Correct 57 ms 15916 KB Output is correct
6 Correct 56 ms 15936 KB Output is correct
7 Correct 54 ms 14660 KB Output is correct
8 Correct 60 ms 19452 KB Output is correct
9 Correct 107 ms 19848 KB Output is correct
10 Correct 87 ms 19468 KB Output is correct
11 Correct 89 ms 19396 KB Output is correct
12 Correct 96 ms 17876 KB Output is correct
13 Correct 100 ms 23880 KB Output is correct
14 Correct 68 ms 15640 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 19896 KB Output is correct
2 Correct 83 ms 17856 KB Output is correct
3 Correct 61 ms 23528 KB Output is correct
4 Correct 96 ms 20024 KB Output is correct
5 Correct 86 ms 19408 KB Output is correct
6 Correct 80 ms 19412 KB Output is correct
7 Correct 87 ms 17820 KB Output is correct
8 Correct 58 ms 23476 KB Output is correct
9 Correct 47 ms 15184 KB Output is correct