oj.uz

답안 #786768

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
786768 2023-07-18T12:41:21 Z trucmai Ball Machine (BOI13_ballmachine) C++17
100 / 100
 108 ms 22564 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});
            //cout<<i<<" "<<out[i]<<endl;    
        }
         
        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 1 ms 2644 KB Output is correct
2 Correct 59 ms 10520 KB Output is correct
3 Correct 37 ms 10624 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 5 ms 3156 KB Output is correct
10 Correct 14 ms 4692 KB Output is correct
11 Correct 58 ms 10472 KB Output is correct
12 Correct 46 ms 10568 KB Output is correct
13 Correct 57 ms 10436 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 6580 KB Output is correct
2 Correct 78 ms 17896 KB Output is correct
3 Correct 45 ms 14252 KB Output is correct
4 Correct 40 ms 7548 KB Output is correct
5 Correct 40 ms 7368 KB Output is correct
6 Correct 40 ms 7432 KB Output is correct
7 Correct 48 ms 6676 KB Output is correct
8 Correct 23 ms 6576 KB Output is correct
9 Correct 74 ms 18328 KB Output is correct
10 Correct 81 ms 17956 KB Output is correct
11 Correct 74 ms 17944 KB Output is correct
12 Correct 83 ms 16052 KB Output is correct
13 Correct 65 ms 20108 KB Output is correct
14 Correct 66 ms 14284 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 10624 KB Output is correct
2 Correct 83 ms 16440 KB Output is correct
3 Correct 70 ms 18564 KB Output is correct
4 Correct 54 ms 15432 KB Output is correct
5 Correct 55 ms 15040 KB Output is correct
6 Correct 53 ms 15108 KB Output is correct
7 Correct 54 ms 13892 KB Output is correct
8 Correct 61 ms 18496 KB Output is correct
9 Correct 84 ms 18464 KB Output is correct
10 Correct 88 ms 18124 KB Output is correct
11 Correct 84 ms 18112 KB Output is correct
12 Correct 82 ms 16448 KB Output is correct
13 Correct 108 ms 22564 KB Output is correct
14 Correct 67 ms 14276 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 18588 KB Output is correct
2 Correct 82 ms 16516 KB Output is correct
3 Correct 58 ms 22404 KB Output is correct
4 Correct 87 ms 18564 KB Output is correct
5 Correct 83 ms 18036 KB Output is correct
6 Correct 73 ms 18080 KB Output is correct
7 Correct 81 ms 16452 KB Output is correct
8 Correct 59 ms 22300 KB Output is correct
9 Correct 46 ms 14284 KB Output is correct