oj.uz

Submission #518315

# Submission time Handle Problem Language Result Execution time Memory
518315 2022-01-23T11:10:33 Z Ai7081 Ball Machine (BOI13_ballmachine) C++17
0 / 100
 166 ms 131076 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const bool debug = 0;

int n, q, p[N][20], op, x, fen[N], L, pos[N];
vector<int> adj[N], ord;
bool mark[N];

void add(int i, int val) {
    for (; i<=n; i+=i&(-i)) fen[i] += val;
    return;
}

int sum(int i) {
    int ret = 0;
    for (; i>0; i-=i&(-i)) ret += fen[i];
    return ret;
}

int find_first(int l, int r) {
    if (l == r) return l;
    int m = (l+r)/2;
    if (sum(m) == 0) find_first(m+1, r);
    else find_first(l, m);
}

void find_ord(int v) {
    for (int i=1; i<=L; i++) p[v][i] = p[p[v][i-1]][i-1];
    for (auto to : adj[v]) {
        if (to == p[v][0]) continue;
        find_ord(to);
    }
    ord.push_back(v);
    return;
}

pair<int, int> find_lift(int v) {
    int ti = 0;
    for (int i=L; i>=0; i--) {
        if (!mark[p[v][i]]) v = p[v][i], ti += pow(2, i);
    }
    return make_pair(v, ti);
}

int main() {
    //scanf(" %d %d", &n, &q);
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> q;
    L = ceil(log2(n+.0));
    for (int i=1; i<=n; i++) {
        //scanf(" %d", &p[i][0]);
        cin >> p[i][0];
        adj[p[i][0]].push_back(i);
    }
    ord.push_back(0);
    find_ord(adj[0][0]);
    for (int i=1; i<=n; i++) pos[ord[i]] = i;
/*
    if (debug) {
        printf("ord : ");
        for (auto it : ord) printf("%d ", it);
        printf("\npos : ");
        for (int i=0; i<=n; i++) printf("%d ", pos[i]);
        printf("\n");
        for (int i=1; i<=n; i++) {
            printf("lift %d : ", i);
            for (int j=0; j<=L; j++) printf("%d ", p[i][j]);
            printf("\n");
        }
    }
*/
    mark[0] = true;
    for (int i=1; i<=n; i++) add(i, 1), mark[i] = true;
    while (q--) {
        //scanf(" %d %d", &op, &x);
        cin >> op >> x;
        if (op == 1) {
            int idx;
            for (int i=1; i<=x; i++) {
                idx = find_first(1, n);
                add(idx, -1);
                mark[ord[idx]] = false;
            }
            //printf("%d\n", ord[idx]);
            cout << ord[idx] << "\n";
        }
        else {
            pair<int, int> p = find_lift(x);
            add(pos[p.first], 1);
            mark[p.first] = true;
            //printf("%d\n", p.second);
            cout << p.second << "\n";
        }
    }

    return 0;
}

/*
8 10
0
1
2
2
3
3
4
6
1 3
2 5
1 1


13 20
0
1
1
2
2
3
3
4
4
5
5
6
6

*/

Compilation message

ballmachine.cpp: In function 'int find_first(int, int)':
ballmachine.cpp:26:1: warning: control reaches end of non-void function [-Wreturn-type]
   26 | }
      | ^

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 77 ms 131076 KB Execution killed with signal 9
2 Runtime error 92 ms 131076 KB Execution killed with signal 9
3 Runtime error 117 ms 131076 KB Execution killed with signal 9
4 Runtime error 77 ms 131076 KB Execution killed with signal 9
5 Runtime error 79 ms 131076 KB Execution killed with signal 9
6 Runtime error 80 ms 131076 KB Execution killed with signal 9
7 Runtime error 76 ms 131076 KB Execution killed with signal 9
8 Runtime error 84 ms 131076 KB Execution killed with signal 9
9 Runtime error 78 ms 131076 KB Execution killed with signal 9
10 Runtime error 80 ms 131076 KB Execution killed with signal 9
11 Runtime error 95 ms 131076 KB Execution killed with signal 9
12 Runtime error 98 ms 131076 KB Execution killed with signal 9
13 Runtime error 104 ms 131076 KB Execution killed with signal 9

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 76 ms 131076 KB Execution killed with signal 9
2 Runtime error 146 ms 131076 KB Execution killed with signal 9
3 Runtime error 101 ms 131076 KB Execution killed with signal 9
4 Runtime error 90 ms 131076 KB Execution killed with signal 9
5 Runtime error 87 ms 131076 KB Execution killed with signal 9
6 Runtime error 99 ms 131076 KB Execution killed with signal 9
7 Runtime error 91 ms 131076 KB Execution killed with signal 9
8 Runtime error 86 ms 131076 KB Execution killed with signal 9
9 Runtime error 117 ms 131076 KB Execution killed with signal 9
10 Runtime error 128 ms 131076 KB Execution killed with signal 9
11 Runtime error 124 ms 131076 KB Execution killed with signal 9
12 Runtime error 127 ms 131076 KB Execution killed with signal 9
13 Runtime error 141 ms 131076 KB Execution killed with signal 9
14 Runtime error 101 ms 131076 KB Execution killed with signal 9

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 86 ms 131076 KB Execution killed with signal 9
2 Runtime error 143 ms 131076 KB Execution killed with signal 9
3 Runtime error 133 ms 131076 KB Execution killed with signal 9
4 Runtime error 125 ms 131076 KB Execution killed with signal 9
5 Runtime error 112 ms 131076 KB Execution killed with signal 9
6 Runtime error 112 ms 131076 KB Execution killed with signal 9
7 Runtime error 109 ms 131076 KB Execution killed with signal 9
8 Runtime error 140 ms 131076 KB Execution killed with signal 9
9 Runtime error 134 ms 131076 KB Execution killed with signal 9
10 Runtime error 158 ms 131076 KB Execution killed with signal 9
11 Runtime error 142 ms 131076 KB Execution killed with signal 9
12 Runtime error 166 ms 131076 KB Execution killed with signal 9
13 Runtime error 146 ms 131076 KB Execution killed with signal 9
14 Runtime error 123 ms 131076 KB Execution killed with signal 9

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 122 ms 131076 KB Execution killed with signal 9
2 Runtime error 126 ms 131076 KB Execution killed with signal 9
3 Runtime error 127 ms 131076 KB Execution killed with signal 9
4 Runtime error 130 ms 131076 KB Execution killed with signal 9
5 Runtime error 135 ms 131076 KB Execution killed with signal 9
6 Runtime error 142 ms 131076 KB Execution killed with signal 9
7 Runtime error 144 ms 131076 KB Execution killed with signal 9
8 Runtime error 163 ms 131076 KB Execution killed with signal 9
9 Runtime error 115 ms 131076 KB Execution killed with signal 9