Submission #799384

#	Time	Username	Problem	Language	Result	Execution time	Memory
799384		serifefedartar	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	261 ms	35548 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 998244353
#define LOGN 20
#define MAXN 100005

vector<vector<int>> graph;
vector<int> sz, mn, id, depth;
int up[LOGN][MAXN], sg[4*MAXN], lazy[4*MAXN];
int now = 0;
void dfs(int node) {
    id[node] = ++now;
    sz[node] = 1;
    mn[node] = node;
    for (auto u : graph[node]) {
        depth[u] = depth[node] + 1;
        up[0][u] = node;
        for (int i = 1; i < LOGN; i++)
            up[i][u] = up[i-1][up[i-1][u]];
        dfs(u);
        sz[node] += sz[u];
        mn[node] = min(mn[node], mn[u]);
    }
}

void init(int k, int a, int b) {
    if (a == b) {
        sg[k] = a;
        return ;
    }
    init(2*k, a, (a+b)/2);
    init(2*k+1, (a+b)/2+1, b);
    sg[k] = sg[2*k] + sg[2*k+1];
}

void range_update(int k, int a, int b, int q_l, int q_r, int x) {
    if (lazy[k] != -1) {
        sg[k] = lazy[k] * (b-a+1);
        if (a != b) {
            lazy[2*k] = lazy[k];
            lazy[2*k+1] = lazy[k];
        }
        lazy[k] = -1;
    }

    if (q_l > b || q_r < a)
        return ;
    if (q_l <= a && b <= q_r) {
        sg[k] = x * (b-a+1);
        if (a != b) {
            lazy[2*k] = x;
            lazy[2*k+1] = x;
        }
        return ;
    }
    range_update(2*k, a, (a+b)/2, q_l, q_r, x);
    range_update(2*k+1, (a+b)/2+1, b, q_l, q_r, x);
    sg[k] = sg[2*k] + sg[2*k+1];
}

int query(int k, int a, int b, int plc) {
    if (lazy[k] != -1) {
        sg[k] = lazy[k] * (b-a+1);
        if (a != b) {
            lazy[2*k] = lazy[k];
            lazy[2*k+1] = lazy[k];
        }
        lazy[k] = -1;
    }

    if (a > plc || plc > b)
        return 0;
    if (a == b)
        return sg[k];
    return query(2*k, a, (a+b)/2, plc) + query(2*k+1, (a+b)/2+1, b, plc);
}

vector<int> priority, order;
void prioritize(int node) {
    vector<pair<int,int>> p;
    for (auto u : graph[node])
        p.push_back({mn[u], u});
    sort(p.begin(), p.end());

    for (auto u : p)
        prioritize(u.s);

    order[node] = priority.size();
    priority.push_back(node);
}

int last_occupied(int node, int old_blank) {
    for (int i = LOGN-1; i >= 0; i--) {
        int nID = id[up[i][node]];
        if (nID > id[old_blank] && nID <= id[old_blank] + sz[old_blank] - 1)
            node = up[i][node];
    }
    return node;
}

int main() {
    fast
    memset(lazy, -1, sizeof(lazy));
    memset(sg, 0, sizeof(sg));
    int N, Q;
    cin >> N >> Q;

    graph = vector<vector<int>>(N+1, vector<int>());
    order = vector<int>(N+1);
    depth = vector<int>(N+1, 0);
    mn = vector<int>(N+1);
    sz = vector<int>(N+1);
    id = vector<int>(N+1);
    for (int i = 1; i <= N; i++) {
        int par; cin >> par;
        graph[par].push_back(i);
    }
    int root = graph[0][0];
    for (int i = 0; i < LOGN; i++)
        up[i][root] = root;
    dfs(root);
    prioritize(root); 
    init(1, 1, N);

    set<int> vacant;
    for (int i = 0; i < N; i++)
        vacant.insert(i);
    while (Q--) {        
        int type;
        cin >> type;
        if (type == 1) {
            int q;
            cin >> q;
            for (int i = 0; i < q; i++) {
                int p = priority[*(vacant.begin())];
                range_update(1, 1, N, id[p], id[p] + sz[p] - 1, (p==root ? -2 : up[0][p]));
                vacant.erase(vacant.begin());
                if (i == q-1)
                    cout << p << "\n";
            }
        } else {
            int q;
            cin >> q;
            int old_blank = query(1, 1, N, id[q]);
            int new_blank = (old_blank == -2 ? root : last_occupied(q, old_blank));
            range_update(1, 1, N, id[new_blank], id[new_blank] + sz[new_blank] - 1, new_blank);
            vacant.insert(order[new_blank]);
            cout << depth[q] - depth[new_blank] << "\n";
        }
    }
}

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