oj.uz

Submission #648191

# Submission time Handle Problem Language Result Execution time Memory
648191 2022-10-05T16:38:04 Z LeonaRaging Ball Machine (BOI13_ballmachine) C++14
100 / 100
 224 ms 32716 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define ll long long
#define pb push_back
#define db(val) "[" #val " = " << (val) << "] "

const ll mod = 1e9 + 7;
const int maxn = 1e5 + 4;
const int INF = 1e9;
const int N = 16;

int n, q, root, f[maxn], h[maxn], up[maxn][20], tin[maxn];
bool has[maxn];
vector<int> adj[maxn];
set<pair<int,int>> mySet;

void dfs(int u) {
    for (int j = 1; j <= N; j++)
        up[u][j] = up[up[u][j - 1]][j - 1];
    f[u] = u;
    for (int v : adj[u]) {
        h[v] = h[u] + 1;
        up[v][0] = u;
        dfs(v);
        f[u] = min(f[u], f[v]);
    }
}

void dfs2(int u) {
    vector<pair<int,int>> ord;
    for (int v : adj[u])
        ord.pb({f[v], v});
    sort(ord.begin(), ord.end());
    for (auto it : ord)
        dfs2(it.se);
    tin[u] = ++tin[0];
    mySet.insert({tin[u], u});
}

int jump(int u) {
    for (int j = N; j >= 0; j--)
        if (has[up[u][j]])
            u = up[u][j];
    return u;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen(".INP", "r", stdin);
    //freopen(".OUT", "w", stdout);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        int p; cin >> p;
        if (p) adj[p].pb(i);
        else root = i;
    }
    dfs(root);
    dfs2(root);
    while (q--) {
        int type; cin >> type;
        if (type == 1) {
            int k; cin >> k;
            while (k--) {
                auto it = *mySet.begin();
                has[it.se] = 1;
                mySet.erase(mySet.begin());
                if (k == 0) cout << it.se << '\n';
            }
        }
        else {
            int u; cin >> u;
            int p = jump(u);
            has[p] = 0;
            mySet.insert({tin[p], p});
            cout << h[u] - h[p] << '\n';
        }
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 120 ms 12924 KB Output is correct
3 Correct 74 ms 13028 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 3 ms 2772 KB Output is correct
9 Correct 7 ms 3284 KB Output is correct
10 Correct 22 ms 5204 KB Output is correct
11 Correct 114 ms 12884 KB Output is correct
12 Correct 71 ms 12984 KB Output is correct
13 Correct 95 ms 12884 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 8320 KB Output is correct
2 Correct 161 ms 25088 KB Output is correct
3 Correct 87 ms 18020 KB Output is correct
4 Correct 63 ms 9456 KB Output is correct
5 Correct 69 ms 9472 KB Output is correct
6 Correct 56 ms 9476 KB Output is correct
7 Correct 57 ms 8064 KB Output is correct
8 Correct 32 ms 8296 KB Output is correct
9 Correct 143 ms 25248 KB Output is correct
10 Correct 182 ms 24924 KB Output is correct
11 Correct 180 ms 24932 KB Output is correct
12 Correct 172 ms 21384 KB Output is correct
13 Correct 124 ms 29036 KB Output is correct
14 Correct 91 ms 18028 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 14024 KB Output is correct
2 Correct 199 ms 22040 KB Output is correct
3 Correct 134 ms 26528 KB Output is correct
4 Correct 132 ms 20784 KB Output is correct
5 Correct 120 ms 20664 KB Output is correct
6 Correct 119 ms 20620 KB Output is correct
7 Correct 120 ms 18080 KB Output is correct
8 Correct 131 ms 26596 KB Output is correct
9 Correct 194 ms 25352 KB Output is correct
10 Correct 206 ms 25216 KB Output is correct
11 Correct 216 ms 25148 KB Output is correct
12 Correct 224 ms 22012 KB Output is correct
13 Correct 193 ms 32716 KB Output is correct
14 Correct 176 ms 18016 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 25544 KB Output is correct
2 Correct 175 ms 22044 KB Output is correct
3 Correct 130 ms 32500 KB Output is correct
4 Correct 174 ms 25664 KB Output is correct
5 Correct 174 ms 25072 KB Output is correct
6 Correct 141 ms 25076 KB Output is correct
7 Correct 202 ms 21956 KB Output is correct
8 Correct 122 ms 32492 KB Output is correct
9 Correct 92 ms 18116 KB Output is correct