oj.uz

Submission #138023

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

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

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

int seg[maxn];

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 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);
    for (int i = 1; i <= N; i++) {
        seg[i] = 1;
    }
    while (Q--) {
        int t; cin >> t;
        if (t == 1) {
            int k; cin >> k;
            int sum = 0;
            for (int i = 1; i <= N; i++) {
                sum += seg[i];
                if (sum == k) {
                    for (int j = 1; j <= i; j++) {
                        seg[j] = 0;
                    }
                    cout << inv[i] << '\n';
                    break;
                }
            }
        }
        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[ord[nxt]] == 0) {
                    res += (1<<k);
                    v = nxt;
                }
            }
            seg[ord[v]] = 1;
            cout << res << '\n';
        }
    }
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2808 KB Output isn't correct
2 Incorrect 67 ms 9592 KB Output isn't correct
3 Execution timed out 1079 ms 9848 KB Time limit exceeded
4 Incorrect 4 ms 2808 KB Output isn't correct
5 Incorrect 4 ms 2808 KB Output isn't correct
6 Incorrect 5 ms 2936 KB Output isn't correct
7 Incorrect 5 ms 2936 KB Output isn't correct
8 Incorrect 5 ms 2936 KB Output isn't correct
9 Incorrect 8 ms 3424 KB Output isn't correct
10 Incorrect 18 ms 4600 KB Output isn't correct
11 Incorrect 71 ms 9592 KB Output isn't correct
12 Execution timed out 1081 ms 9720 KB Time limit exceeded
13 Incorrect 93 ms 9592 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 6152 KB Output is correct
2 Incorrect 136 ms 15788 KB Output isn't correct
3 Execution timed out 1066 ms 12836 KB Time limit exceeded
4 Incorrect 45 ms 6904 KB Output isn't correct
5 Incorrect 45 ms 6776 KB Output isn't correct
6 Incorrect 55 ms 6904 KB Output isn't correct
7 Incorrect 45 ms 6260 KB Output isn't correct
8 Correct 31 ms 6136 KB Output is correct
9 Incorrect 103 ms 15992 KB Output isn't correct
10 Incorrect 119 ms 15628 KB Output isn't correct
11 Incorrect 108 ms 15544 KB Output isn't correct
12 Incorrect 106 ms 14328 KB Output isn't correct
13 Correct 77 ms 17400 KB Output is correct
14 Execution timed out 1077 ms 12916 KB Time limit exceeded

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 9540 KB Output isn't correct
2 Incorrect 119 ms 14508 KB Output isn't correct
3 Correct 130 ms 16092 KB Output is correct
4 Incorrect 80 ms 13416 KB Output isn't correct
5 Incorrect 81 ms 13048 KB Output isn't correct
6 Incorrect 77 ms 13048 KB Output isn't correct
7 Incorrect 74 ms 12152 KB Output isn't correct
8 Correct 90 ms 15992 KB Output is correct
9 Incorrect 131 ms 16060 KB Output isn't correct
10 Incorrect 132 ms 15736 KB Output isn't correct
11 Incorrect 127 ms 15660 KB Output isn't correct
12 Incorrect 121 ms 14596 KB Output isn't correct
13 Correct 152 ms 19436 KB Output is correct
14 Incorrect 80 ms 12660 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 164 ms 16168 KB Output isn't correct
2 Incorrect 121 ms 14428 KB Output isn't correct
3 Correct 106 ms 19308 KB Output is correct
4 Incorrect 124 ms 16120 KB Output isn't correct
5 Incorrect 132 ms 15740 KB Output isn't correct
6 Incorrect 108 ms 15608 KB Output isn't correct
7 Incorrect 116 ms 14460 KB Output isn't correct
8 Correct 92 ms 19320 KB Output is correct
9 Execution timed out 1062 ms 12984 KB Time limit exceeded