oj.uz

Submission #99800

# Submission time Handle Problem Language Result Execution time Memory
99800 2019-03-07T12:35:13 Z PeppaPig Ball Machine (BOI13_ballmachine) C++14
100 / 100
 319 ms 23904 KB 
#include <bits/stdc++.h>

#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 1e5+5;

int n, q, rot;
int mn[N], dep[N], par[N][18];
int pos[N], chk[N];
vector<int> g[N], V;
priority_queue<pii, vector<pii>, greater<pii> > Q;

int proc(int u, int p) {
    par[u][0] = p, dep[u] = dep[p] + 1, mn[u] = u;
    for(int i = 1; i <= 17; i++) par[u][i] = par[par[u][i-1]][i-1];

    for(int v : g[u]) mn[u] = min(mn[u], proc(v, u));
    sort(g[u].begin(), g[u].end(), [&](const int &a, const int &b) {
        return mn[a] < mn[b];
    });
    return mn[u];
}

void dfs(int u) {
    for(int v : g[u]) dfs(v);
    V.emplace_back(u);
}

int main() {
    scanf("%d %d", &n, &q);
    for(int i = 1, a; i <= n; i++) {
        scanf("%d", &a);
        if(a) g[a].emplace_back(i);
        else rot = i;
    }
    proc(rot, 0), dfs(rot);
    for(int i = 1; i <= n; i++) pos[V[i-1]] = i;
    for(int i = 1; i <= n; i++) Q.emplace(pos[i], i);
    for(int i = 1, T, a; i <= q; i++) {
        scanf("%d %d", &T, &a);
        if(T == 1) {
            int now = -1;
            while(a--) {
                pii u = Q.top(); Q.pop();
                chk[u.y] = true;
                now = u.y;
            }
            printf("%d\n", now);
        } else {
            int b = a;
            for(int i = 17; ~i; i--) if(chk[par[b][i]]) b = par[b][i];
            chk[b] = false;
            Q.emplace(pos[b], b);
            printf("%d\n", dep[a] - dep[b]);
        }
    }

    return 0;
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &q);
     ~~~~~^~~~~~~~~~~~~~~~~
ballmachine.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a);
         ~~~~~^~~~~~~~~~
ballmachine.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &T, &a);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 134 ms 11604 KB Output is correct
3 Correct 75 ms 11348 KB Output is correct
4 Correct 5 ms 2732 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 5 ms 2816 KB Output is correct
7 Correct 6 ms 2816 KB Output is correct
8 Correct 6 ms 2720 KB Output is correct
9 Correct 14 ms 3336 KB Output is correct
10 Correct 31 ms 4984 KB Output is correct
11 Correct 177 ms 11808 KB Output is correct
12 Correct 95 ms 11508 KB Output is correct
13 Correct 152 ms 11628 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 7156 KB Output is correct
2 Correct 266 ms 19592 KB Output is correct
3 Correct 109 ms 14668 KB Output is correct
4 Correct 103 ms 8408 KB Output is correct
5 Correct 109 ms 8280 KB Output is correct
6 Correct 96 ms 8172 KB Output is correct
7 Correct 88 ms 7468 KB Output is correct
8 Correct 46 ms 7028 KB Output is correct
9 Correct 271 ms 19764 KB Output is correct
10 Correct 219 ms 19184 KB Output is correct
11 Correct 186 ms 19180 KB Output is correct
12 Correct 230 ms 17384 KB Output is correct
13 Correct 172 ms 20960 KB Output is correct
14 Correct 128 ms 14820 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 11400 KB Output is correct
2 Correct 247 ms 17880 KB Output is correct
3 Correct 187 ms 19424 KB Output is correct
4 Correct 165 ms 16228 KB Output is correct
5 Correct 180 ms 15984 KB Output is correct
6 Correct 180 ms 15900 KB Output is correct
7 Correct 188 ms 14620 KB Output is correct
8 Correct 192 ms 19564 KB Output is correct
9 Correct 238 ms 20020 KB Output is correct
10 Correct 280 ms 19504 KB Output is correct
11 Correct 251 ms 19488 KB Output is correct
12 Correct 240 ms 17904 KB Output is correct
13 Correct 319 ms 23904 KB Output is correct
14 Correct 165 ms 15580 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 19944 KB Output is correct
2 Correct 299 ms 17896 KB Output is correct
3 Correct 190 ms 23204 KB Output is correct
4 Correct 267 ms 20080 KB Output is correct
5 Correct 268 ms 19312 KB Output is correct
6 Correct 226 ms 19432 KB Output is correct
7 Correct 249 ms 17948 KB Output is correct
8 Correct 181 ms 23148 KB Output is correct
9 Correct 114 ms 14764 KB Output is correct