oj.uz

Submission #138025

# Submission time Handle Problem Language Result Execution time Memory
138025 2019-07-29T01:19:15 Z silxikys Ball Machine (BOI13_ballmachine) C++14
16.1111 / 100
 160 ms 19320 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 1e5+5;
int N, Q;
vector<int> adj[maxn];

int minsub[maxn];
int ord[maxn], inv[maxn]; //node to seg, seg to node
int pt = 1;

void prep(int i) {
    minsub[i] = i;
    for (int j: adj[i]) {
        minsub[i] = min(minsub[i],minsub[j]);
    }
    sort(adj[i].begin(),adj[i].end(),[](int a, int b) {
            return minsub[a] < minsub[b];
            });
}
void dfs(int i) {
    for (int j: adj[i]) {
        dfs(j);
    }
    ord[i] = pt;
    inv[pt] = i;
    pt++;
    //cout << i << ' ';
}

const int maxk = 18;
int par[maxk][maxn];

int seg[maxn];

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> Q;
    int rt = -1;
    for (int i = 1; i <= N; i++) {
        int pi; cin >> pi;
        if (pi == 0) rt = i;
        else adj[pi].push_back(i);
        par[0][i] = pi;
    }
    for (int k = 1; k < maxk; k++) {
        for (int i = 1; i <= N; i++) {
            par[k][i] = par[k-1][par[k-1][i]];
        }
    }
    prep(rt);
    dfs(rt);
    while (Q--) {
        int t; cin >> t;
        if (t == 1) {
            int k; cin >> k;
            for (int i = 1; i <= k; i++) {
                seg[inv[i]] = 1;
            }
            cout << inv[k] << '\n';
        }
        else {
            int v; cin >> v;
            int res = 0;
            for (int k = maxk - 1; k >= 0; k--) {
                if (par[k][v] == 0) continue;
                int nxt = par[k][v];
                if (seg[nxt] == 1) {
                    res += (1<<k);
                    v = nxt;
                }
            }
            seg[v] = 0;
            cout << res << '\n';
        }
    }
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2808 KB Output isn't correct
2 Incorrect 87 ms 9464 KB Output isn't correct
3 Incorrect 52 ms 9208 KB Output isn't correct
4 Incorrect 4 ms 2808 KB Output isn't correct
5 Incorrect 5 ms 2808 KB Output isn't correct
6 Incorrect 4 ms 2808 KB Output isn't correct
7 Incorrect 4 ms 2936 KB Output isn't correct
8 Incorrect 4 ms 2940 KB Output isn't correct
9 Incorrect 8 ms 3192 KB Output isn't correct
10 Incorrect 16 ms 4472 KB Output isn't correct
11 Incorrect 67 ms 9464 KB Output isn't correct
12 Incorrect 52 ms 9208 KB Output isn't correct
13 Incorrect 63 ms 9436 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 5852 KB Output is correct
2 Incorrect 97 ms 15452 KB Output isn't correct
3 Incorrect 59 ms 12276 KB Output isn't correct
4 Incorrect 48 ms 6776 KB Output isn't correct
5 Incorrect 44 ms 6648 KB Output isn't correct
6 Incorrect 43 ms 6708 KB Output isn't correct
7 Incorrect 43 ms 6136 KB Output isn't correct
8 Correct 31 ms 5880 KB Output is correct
9 Incorrect 143 ms 15836 KB Output isn't correct
10 Incorrect 102 ms 15372 KB Output isn't correct
11 Incorrect 93 ms 15608 KB Output isn't correct
12 Incorrect 102 ms 14028 KB Output isn't correct
13 Correct 78 ms 17016 KB Output is correct
14 Incorrect 60 ms 12404 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 9344 KB Output isn't correct
2 Incorrect 116 ms 14416 KB Output isn't correct
3 Correct 92 ms 16036 KB Output is correct
4 Incorrect 78 ms 13304 KB Output isn't correct
5 Incorrect 74 ms 13048 KB Output isn't correct
6 Incorrect 92 ms 12920 KB Output isn't correct
7 Incorrect 78 ms 12024 KB Output isn't correct
8 Correct 94 ms 15992 KB Output is correct
9 Incorrect 119 ms 16120 KB Output isn't correct
10 Incorrect 123 ms 15608 KB Output isn't correct
11 Incorrect 123 ms 15608 KB Output isn't correct
12 Incorrect 119 ms 14364 KB Output isn't correct
13 Correct 160 ms 19320 KB Output is correct
14 Incorrect 92 ms 12532 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 120 ms 15932 KB Output isn't correct
2 Incorrect 118 ms 14292 KB Output isn't correct
3 Correct 93 ms 18812 KB Output is correct
4 Incorrect 111 ms 15864 KB Output isn't correct
5 Incorrect 113 ms 15500 KB Output isn't correct
6 Incorrect 100 ms 15480 KB Output isn't correct
7 Incorrect 146 ms 14480 KB Output isn't correct
8 Correct 109 ms 18860 KB Output is correct
9 Incorrect 72 ms 12300 KB Output isn't correct