oj.uz

답안 #730432

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
730432 2023-04-25T21:29:12 Z thimote75 Ball Machine (BOI13_ballmachine) C++14
97.1429 / 100
 1000 ms 38412 KB 
#include <bits/stdc++.h>

using namespace std;

#define vi vector<int>
#define gi vector<vi>
#define pq priority_queue<pair<int, int>>
#define sq set<int>

vi parents;
gi parents_2k;
gi roads;
vi postorder;
vi rev_pord;
vi subtree;
sq omega;

int init_ddfs ( int node, int parent ) {
    int min_s = node;
    pq rebase;

    for (int next : roads[node]) {
        int loc_s = init_ddfs(next, node);
        rebase.push({ - loc_s, next });
        min_s = min(min_s, loc_s);
    }

    roads[node].clear();
    while (rebase.size() != 0) {
        auto u = rebase.top(); rebase.pop();

        roads[node].push_back(u.second);
    }

    return min_s;
}
int dfs (int node, int parent) {
    subtree[node] = 1;
    for (int next : roads[node])
        subtree[node] += dfs(next, node);
    
    postorder.push_back(node);
    return subtree[node];
}
int jump (int n, int k) {
    for (int i = 0; i < 20; i ++)
        if (n != -1 && (1 << i) & k)
            n = parents_2k[n][i];
    return n;
}

int main () {
    int N, Q;
    cin >> N >> Q;

    int root;
    parents.resize(N);
    roads  .resize(N);
    subtree.resize(N);

    parents_2k.resize(N, vi(20, -1));

    for (int i = 0; i < N; i ++) {
        cin >> parents[i]; parents[i] --;
        parents_2k[i][0] = parents[i];

        if (parents[i] == -1) root = i;
        else {
            roads[parents[i]].push_back(i);
        }
    }

    init_ddfs(root, -1);
    dfs(root, -1);

    for (int k = 0; k + 1 < 20; k ++) {
        for (int i = 0; i < N; i ++) {
            if (parents_2k[i][k] == -1) continue ;

            parents_2k[i][k + 1]
             = parents_2k[parents_2k[i][k]][k];
        }
    }

    rev_pord.resize(N);
    for (int i = 0; i < N; i ++)
        rev_pord[postorder[i]] = i;
    for (int i = 0; i < N; i ++)
        omega.insert(rev_pord[i]);

    for (int q = 0; q < Q; q ++) {
        int t, k;
        cin >> t >> k;

        if (t == 1) {
            for (int _k = k - 1; _k >= 0; _k --) {
                auto h = *omega.begin();
                omega.erase(h);

                if (_k == 0)
                    cout << postorder[h] + 1 << endl;
            }
        } else {
            k --;
    
            int a = 0;
            int b = 1 << 20;
            while (b - a > 1) {
                int c = (a + b) >> 1;
                int m = jump(k, c);

                if (m == -1 || omega.find(rev_pord[m]) != omega.end())
                    b = c;
                else a = c;
            }

            int n = jump(k, a);
            omega.insert(rev_pord[n]);

            cout << a << endl;
        }
        
    }
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:75:8: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   75 |     dfs(root, -1);
      |     ~~~^~~~~~~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 368 ms 14848 KB Output is correct
3 Correct 269 ms 15048 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 24 ms 1208 KB Output is correct
10 Correct 66 ms 3916 KB Output is correct
11 Correct 432 ms 14852 KB Output is correct
12 Correct 252 ms 15056 KB Output is correct
13 Correct 358 ms 14840 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 194 ms 7340 KB Output is correct
2 Correct 656 ms 29892 KB Output is correct
3 Correct 288 ms 22156 KB Output is correct
4 Correct 317 ms 9364 KB Output is correct
5 Correct 341 ms 9212 KB Output is correct
6 Correct 331 ms 9220 KB Output is correct
7 Correct 325 ms 7600 KB Output is correct
8 Correct 255 ms 7428 KB Output is correct
9 Correct 515 ms 30260 KB Output is correct
10 Correct 661 ms 29828 KB Output is correct
11 Correct 685 ms 29828 KB Output is correct
12 Correct 689 ms 25800 KB Output is correct
13 Correct 352 ms 33880 KB Output is correct
14 Correct 333 ms 22252 KB Output is correct

Subtask #3
37.1428571429 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 268 ms 15464 KB Output is correct
2 Correct 804 ms 26480 KB Output is correct
3 Correct 573 ms 30664 KB Output is correct
4 Correct 460 ms 24464 KB Output is correct
5 Correct 501 ms 23948 KB Output is correct
6 Correct 486 ms 24132 KB Output is correct
7 Correct 591 ms 21120 KB Output is correct
8 Correct 753 ms 30644 KB Output is correct
9 Correct 770 ms 30352 KB Output is correct
10 Correct 828 ms 30020 KB Output is correct
11 Correct 829 ms 30124 KB Output is correct
12 Correct 799 ms 26488 KB Output is correct
13 Execution timed out 1076 ms 38412 KB Time limit exceeded
14 Correct 409 ms 22224 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 873 ms 30572 KB Output is correct
2 Correct 813 ms 26580 KB Output is correct
3 Correct 373 ms 38268 KB Output is correct
4 Correct 885 ms 30544 KB Output is correct
5 Correct 903 ms 30008 KB Output is correct
6 Correct 624 ms 30112 KB Output is correct
7 Correct 884 ms 26380 KB Output is correct
8 Correct 392 ms 38276 KB Output is correct
9 Correct 284 ms 22220 KB Output is correct