Submission #518331

#	Time	Username	Problem	Language	Result	Execution time	Memory
518331		Ai7081	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	196 ms	21928 KiB

ballmachine

#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], mi[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) return find_first(m+1, r);
    else return find_first(l, m);
}

void find_min(int v) {
    for (int i=1; i<=L; i++) p[v][i] = p[p[v][i-1]][i-1];
    mi[v] = v;
    for (auto to : adj[v]) {
        find_min(to);
        mi[v] = min(mi[v], mi[to]);
    }
    return;
}

void find_ord(int v) {
    for (auto to : adj[v]) {
        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);
}

bool cmp(int i, int j) {
    return mi[i] < mi[j];
}

int main() {
    scanf(" %d %d", &n, &q);
    L = ceil(log2(n + 1));
    for (int i=1; i<=n; i++) {
        scanf(" %d", &p[i][0]);
        adj[p[i][0]].push_back(i);
    }

    find_min(adj[0][0]);
    for (int i=1; i<=n; i++) sort(adj[i].begin(), adj[i].end(), cmp);

    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);
        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]);
        }
        else {
            pair<int, int> out = find_lift(x);
            add(pos[out.first], 1);
            mark[out.first] = true;
            printf("%d\n", out.second);
        }

        if (debug) {
            printf("sum : ");
            for (int i=1; i<=n; i++) printf("%d ", sum(i));
            printf("\n");
        }
    }

    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |     scanf(" %d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
ballmachine.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         scanf(" %d", &p[i][0]);
      |         ~~~~~^~~~~~~~~~~~~~~~~
ballmachine.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         scanf(" %d %d", &op, &x);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
ballmachine.cpp:97:35: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   97 |             printf("%d\n", ord[idx]);
      |                                   ^

• Subtask 1: 25 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5