Submission #559765

#	Time	Username	Problem	Language	Result	Execution time	Memory
559765		hoanghq2004	Ball Machine (BOI13_ballmachine)	C++14	0 / 100	117 ms	15668 KiB

ballmachine

#include <bits/stdc++.h>

using namespace std;

int n, q;
vector <int> e[100010];
int ti, pos[100010], ord[100010];
int minc[100010];

void dfs1(int u) {
    minc[u] = n + 1;
    for (auto v: e[u]) {
        dfs1(v);
        if (minc[v] < minc[u]) {
            minc[u] = minc[v];
        }
    }
    minc[u] = min(minc[u], u);
}

void dfs2(int u) {
    ord[ti] = u;
    pos[u] = ti--;
    for (auto v: e[u]) dfs2(v);
}

int st[400010];

void update(int id, int l, int r, int i, int val) {
    if (i > r || i < l) return;
    if (l == r) {
        st[id] = 1;
        return;
    }
    int mid = l + r >> 1;
    update(id * 2, l, mid, i, val);
    update(id * 2 + 1, mid + 1, r, i, val);
    st[id] = min(st[id * 2], st[id * 2 + 1]);
}

int get(int id, int l, int r) {
    if (l == r) return l;
    int mid = l + r >> 1;
    if (st[id * 2] == 0) return get(id * 2, l, mid);
    else return get(id * 2 + 1, mid + 1, r);
}

int cmp(int u, int v) {
    return minc[u] > minc[v];
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i) {
        int p;
        scanf("%d", &p);
        e[p].push_back(i);
    }
    ti = n;
    dfs1(e[0].front());
    for (int u = 1; u <= n; ++u)
        sort(e[u].begin(), e[u].end(), cmp);
    dfs2(e[0].front());
//    for (int i = 1; i <= n; ++i) cout << ord[i] << " ";
    while (q--) {
        int c, k;
        scanf("%d%d", &c, &k);
        if (c == 1) {
            int ans = 0;
            while (k--) {
                ans = get(1, 1, n);
                update(1, 1, n, ans, 1);
            }
            cout << ord[ans] << "\n";
        }
        else {
            update(1, 1, n, k, 0);
            cout << "0\n";
        }
    }
}

Compilation message (stderr)

ballmachine.cpp: In function 'void update(int, int, int, int, int)':
ballmachine.cpp:35:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |     int mid = l + r >> 1;
      |               ~~^~~
ballmachine.cpp: In function 'int get(int, int, int)':
ballmachine.cpp:43:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |     int mid = l + r >> 1;
      |               ~~^~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |     scanf("%d%d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~
ballmachine.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         scanf("%d", &p);
      |         ~~~~~^~~~~~~~~~
ballmachine.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         scanf("%d%d", &c, &k);
      |         ~~~~~^~~~~~~~~~~~~~~~

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