Submission #695396

#	Time	Username	Problem	Language	Result	Execution time	Memory
695396		Duy_e	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	206 ms	24988 KiB

ballmachine

#include <bits/stdc++.h>
#define ll long long
#define pii pair <ll, ll>
#define nd second
#define st first
#define rep(i, n, m) for (ll i = n; i <= m; i ++)
#define rrep(i, n, m) for (ll i = n; i >= m; i --)
using namespace std;
const long long N = 2e5 + 5;
int n, q, a[N], full[N], mi[N], up[20][N], pos[N];
vector <int> d[N], order;

void dfs(int u) {
    mi[u] = u;
    for (int v: d[u])
        dfs(v), mi[u] = min(mi[u], mi[v]);
}

void dfs2(int u) {
    for (int v: d[u]) dfs2(v);
    order.push_back(u);
}

priority_queue <pii, vector <pii>, greater <pii>> st;
void del(int u) {
    int cnt = 0;
    rrep(i, 19, 0) if (full[up[i][u]])
        u = up[i][u], cnt += 1 << i;
    full[u] = false;
    st.push({pos[u], u});
    cout << cnt << '\n';
}

int cur = 0;
void add(int k) {
    int lst = 0;
    while (st.size() && k) {
        lst = st.top().nd;
        st.pop();
        k --;
        full[lst] = true;
    }

    while (k) k --, lst = order[cur ++], full[lst] = true;
    cout << lst << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("A.ans", "w", stdout);
    cin >> n >> q;
    rep(i, 1, n) {
        int p; cin >> p;
        d[p].push_back(i);
        up[0][i] = p;
    }

    dfs(0);
    rep(i, 1, 19) rep(j, 1, n)
        up[i][j] = up[i - 1][up[i - 1][j]];

    auto cmp = [&] (int u, int v) { return mi[u] < mi[v]; };
    rep(i, 1, n) sort(d[i].begin(), d[i].end(), cmp);

    dfs2(0);
    rep(i, 0, order.size() - 1) pos[order[i]] = i;
    int t, x;

    while (q --) {
        cin >> t >> x;
        if (t == 1) add(x);
        if (t == 2) del(x);
    }

    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:6:39: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define rep(i, n, m) for (ll i = n; i <= m; i ++)
......
   67 |     rep(i, 0, order.size() - 1) pos[order[i]] = i;
      |         ~~~~~~~~~~~~~~~~~~~~~~         
ballmachine.cpp:67:5: note: in expansion of macro 'rep'
   67 |     rep(i, 0, order.size() - 1) pos[order[i]] = i;
      |     ^~~

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