oj.uz

Submission #708476

# Submission time Handle Problem Language Result Execution time Memory
708476 2023-03-11T20:04:33 Z stevancv Ball Machine (BOI13_ballmachine) C++14
100 / 100
 338 ms 27964 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 5;
const ll linf = 1e18;
const int mod = 1e9 + 7;
vector<int> g[N];
int lift[N][17], mn[N], order[N], out[N], tsz;
void Dfs(int s, int e) {
    mn[s] = s;
    lift[s][0] = e;
    for (int i = 1; i < 17; i++) lift[s][i] = lift[lift[s][i - 1]][i - 1];
    for (int u : g[s]) {
        if (u != e) {
            Dfs(u, s);
            smin(mn[s], mn[u]);
        }
    }
}
void Dfs1(int s, int e) {
    for (int u : g[s]) {
        if (u != e) {
            Dfs1(u, s);
        }
    }
    out[s] = ++tsz;
    order[tsz] = s;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    int root = 0;
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        if (x == 0) root = i;
        else g[x].push_back(i);
    }
    Dfs(root, 0);
    for (int i = 1; i <= n; i++) {
        sort(g[i].begin(), g[i].end(), [&] (int xx, int yy) {
            return mn[xx] < mn[yy];
        });
    }
    Dfs1(root, 0);
    set<int> s;
    for (int i = 1; i <= n; i++) s.insert(i);
    while (q--) {
        int ty, x;
        cin >> ty >> x;
        if (ty == 1) {
            int res = -1;
            while (x--) {
                res = *s.begin();
                s.erase(res);
            }
            cout << order[res] << en;
            continue;
        }
        int ans = 0;
        for (int i = 16; i >= 0; i--) {
            int who = lift[x][i];
            if (s.find(out[who]) == s.end() && who > 0) {
                ans += 1 << i;
                x = who;
            }
        }
        s.insert(out[x]);
        cout << ans << en;
    }
    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 157 ms 13188 KB Output is correct
3 Correct 82 ms 13252 KB Output is correct
4 Correct 2 ms 2656 KB Output is correct
5 Correct 2 ms 2680 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 3 ms 2772 KB Output is correct
8 Correct 3 ms 2812 KB Output is correct
9 Correct 9 ms 3284 KB Output is correct
10 Correct 27 ms 5236 KB Output is correct
11 Correct 161 ms 13184 KB Output is correct
12 Correct 74 ms 13196 KB Output is correct
13 Correct 136 ms 13200 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 7656 KB Output is correct
2 Correct 309 ms 22712 KB Output is correct
3 Correct 111 ms 17608 KB Output is correct
4 Correct 108 ms 9136 KB Output is correct
5 Correct 149 ms 9056 KB Output is correct
6 Correct 142 ms 9036 KB Output is correct
7 Correct 138 ms 8012 KB Output is correct
8 Correct 42 ms 7720 KB Output is correct
9 Correct 235 ms 23172 KB Output is correct
10 Correct 291 ms 22556 KB Output is correct
11 Correct 268 ms 22568 KB Output is correct
12 Correct 266 ms 20176 KB Output is correct
13 Correct 136 ms 24868 KB Output is correct
14 Correct 105 ms 17648 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 13004 KB Output is correct
2 Correct 305 ms 20764 KB Output is correct
3 Correct 206 ms 22604 KB Output is correct
4 Correct 153 ms 18972 KB Output is correct
5 Correct 213 ms 18564 KB Output is correct
6 Correct 188 ms 18508 KB Output is correct
7 Correct 200 ms 17020 KB Output is correct
8 Correct 215 ms 22764 KB Output is correct
9 Correct 238 ms 23072 KB Output is correct
10 Correct 294 ms 22740 KB Output is correct
11 Correct 288 ms 22736 KB Output is correct
12 Correct 288 ms 20768 KB Output is correct
13 Correct 323 ms 27964 KB Output is correct
14 Correct 140 ms 18040 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 23352 KB Output is correct
2 Correct 308 ms 20716 KB Output is correct
3 Correct 157 ms 27656 KB Output is correct
4 Correct 251 ms 23216 KB Output is correct
5 Correct 338 ms 22752 KB Output is correct
6 Correct 295 ms 22624 KB Output is correct
7 Correct 289 ms 20700 KB Output is correct
8 Correct 155 ms 27596 KB Output is correct
9 Correct 121 ms 17652 KB Output is correct