oj.uz

Submission #799384

# Submission time Handle Problem Language Result Execution time Memory
799384 2023-07-31T13:38:56 Z serifefedartar Ball Machine (BOI13_ballmachine) C++17
100 / 100
 261 ms 35548 KB 
#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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3540 KB Output is correct
2 Correct 147 ms 16316 KB Output is correct
3 Correct 65 ms 16328 KB Output is correct
4 Correct 2 ms 3540 KB Output is correct
5 Correct 2 ms 3592 KB Output is correct
6 Correct 2 ms 3668 KB Output is correct
7 Correct 3 ms 3668 KB Output is correct
8 Correct 3 ms 3728 KB Output is correct
9 Correct 9 ms 4372 KB Output is correct
10 Correct 32 ms 6704 KB Output is correct
11 Correct 145 ms 16424 KB Output is correct
12 Correct 63 ms 16320 KB Output is correct
13 Correct 140 ms 16336 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 9832 KB Output is correct
2 Correct 217 ms 28492 KB Output is correct
3 Correct 83 ms 22360 KB Output is correct
4 Correct 100 ms 11552 KB Output is correct
5 Correct 93 ms 11592 KB Output is correct
6 Correct 97 ms 11460 KB Output is correct
7 Correct 95 ms 10012 KB Output is correct
8 Correct 36 ms 9872 KB Output is correct
9 Correct 195 ms 28988 KB Output is correct
10 Correct 220 ms 28628 KB Output is correct
11 Correct 187 ms 28556 KB Output is correct
12 Correct 198 ms 25344 KB Output is correct
13 Correct 111 ms 31836 KB Output is correct
14 Correct 86 ms 22272 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 16344 KB Output is correct
2 Correct 231 ms 25892 KB Output is correct
3 Correct 149 ms 29176 KB Output is correct
4 Correct 145 ms 24088 KB Output is correct
5 Correct 137 ms 23784 KB Output is correct
6 Correct 143 ms 23756 KB Output is correct
7 Correct 149 ms 21372 KB Output is correct
8 Correct 147 ms 29252 KB Output is correct
9 Correct 230 ms 29060 KB Output is correct
10 Correct 253 ms 28864 KB Output is correct
11 Correct 244 ms 28668 KB Output is correct
12 Correct 231 ms 25832 KB Output is correct
13 Correct 231 ms 35548 KB Output is correct
14 Correct 191 ms 22336 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 29336 KB Output is correct
2 Correct 241 ms 26012 KB Output is correct
3 Correct 119 ms 35372 KB Output is correct
4 Correct 238 ms 29296 KB Output is correct
5 Correct 232 ms 28760 KB Output is correct
6 Correct 196 ms 28624 KB Output is correct
7 Correct 228 ms 25800 KB Output is correct
8 Correct 127 ms 35384 KB Output is correct
9 Correct 84 ms 22340 KB Output is correct