oj.uz

Submission #1015919

# Submission time Handle Problem Language Result Execution time Memory
1015919 2024-07-07T04:49:26 Z caterpillow Ball Machine (BOI13_ballmachine) C++17
100 / 100
 290 ms 22352 KB 
#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end() 
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
const ll INF = 1e18;
const int inf = 1e9;

template<template<typename> class Container, typename T>
ostream& operator<<(ostream& os, Container<T> o) {
    os << "{"; 
    int g = size(o); 
    for (auto i : o) os << i << ((--g) == 0 ? "" : ", "); 
    os << "}";
    return os;
}

void _print() {
    cerr << "\n";
}

template<typename T, typename ...V>
void _print(T t, V... v) {
    cerr << t; if (sizeof...(v)) cerr << ", "; _print(v...);
}

#ifdef LOCAL
#define dbg(x...) cerr << #x << " = "; _print(x);
#else
#define dbg(x...)
#define cerr if (0) std::cerr
#endif

/*

removing a ball just deletes its most ancestor ancestor
balls have a fixed "preferred path" at any given state

if a node has a ball in it, then so does its entire subtree

given some tree, there is a fixed priority among active nodes

*/

#ifdef LOCAL
const int sz = 1 << 4;
#else
const int sz = 1 << 17;
#endif

struct LazySeg {
    vt<int> seg, lazy;
    void init() {
        seg.resize(2 * sz, 1);
        lazy.resize(2 * sz, -1);
        ROF (i, 1, sz) seg[i] = seg[2 * i] + seg[2 * i + 1]; 
    }
    void pull(int i) {
        seg[i] = seg[2 * i] + seg[2 * i + 1]; 
    }
    void push(int i, int l, int r) {
        if (lazy[i] == -1) return;
        seg[i] = lazy[i] * (r - l + 1);
        if (l != r) F0R (j, 2) lazy[2 * i + j] = lazy[i]; 
        lazy[i] = -1;
    }
    void upd(int lo, int hi, int v, int i = 1, int l = 0, int r = sz - 1) {
        push(i, l, r);
        if (lo > r || hi < l) return;
        if (lo <= l && r <= hi) {
            lazy[i] = v;
            push(i, l, r);
            return;
        }
        int m = (l + r) / 2;
        upd(lo, hi, v, 2 * i, l, m);
        upd(lo, hi, v, 2 * i + 1, m + 1, r);
        pull(i);
    }
    int query(int lo, int hi, int i = 1, int l = 0, int r = sz - 1) {
        push(i, l, r);
        if (lo > r || hi < l) return 0;
        if (lo <= l && r <= hi) return seg[i];
        int m = (l + r) / 2;
        return query(lo, hi, 2 * i, l, m) + query(lo, hi, 2 * i + 1, m + 1, r);
    }
    int walk(int k, int i = 1, int l = 0, int r = sz - 1) {
        if (l == r) return l;
        int m = (l + r) / 2;
        push(2 * i, l, m), push(2 * i + 1, m + 1, r);
        if (seg[2 * i] >= k) return walk(k, 2 * i, l, m);
        else return walk(k - seg[2 * i], 2 * i + 1, m + 1, r);
    }
};

int n, q, t; 
vt<int> adj[100005];
vt<int> depth, pri, rpri, mn;
LazySeg seg;

int jmp[17][100005];
int maxd;

int dp(int u) {
    int res = u;
    for (int v : adj[u]) {
        res = min(res, dp(v));
    }
    return mn[u] = res;
}

void dfs(int u, int p = -1) {
    for (int v : adj[u]) {
        depth[v] = depth[u] + 1;
        dfs(v, u);
    }
    rpri[t] = u;    
    pri[u] = t++;
}

int lift(int u) {
    auto good = [&] (int v) {
        return seg.query(pri[v], pri[v]) == 0;  
    };
    ROF (i, 0, maxd) {
        if (good(jmp[i][u])) u = jmp[i][u];
    }
    return u;
}


main() {
    cin.tie(0)->sync_with_stdio(0);
    
    cin >> n >> q;
    depth = pri = rpri = mn = vt<int>(n);
    int rt = -1;
    F0R (i, n) {
        int p; cin >> p;
        p--;
        if (p >= 0) {
            jmp[0][i] = p;
            adj[p].pb(i);
        } else {
            rt = i;
            jmp[0][rt] = rt;
        }
    }
    while ((1 << maxd) <= n) maxd++;
    FOR (i, 1, maxd) {
        F0R (u, n) {
            jmp[i][u] = jmp[i - 1][jmp[i - 1][u]];
        }
    }

    seg.init();
    dp(rt);
    F0R (i, n) sort(all(adj[i]), [&] (int u, int v) { return mn[u] < mn[v]; });
    dfs(rt, rt);

    F0R (i, q) {
        int t, u; cin >> t >> u;
        if (t == 1) { // insert balls
            int r = seg.walk(u);
            seg.upd(0, r, 0);
            cout << rpri[r] + 1 << endl;
        } else if (t == 2) {
            u--;
            int v = lift(u);
            seg.upd(pri[v], pri[v], 1);
            cout << depth[u] - depth[v] << endl;
        } else assert(0);
    }
}

Compilation message

ballmachine.cpp:147:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  147 | main() {
      | ^~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4696 KB Output is correct
2 Correct 187 ms 12368 KB Output is correct
3 Correct 84 ms 12024 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 3 ms 4952 KB Output is correct
7 Correct 3 ms 4956 KB Output is correct
8 Correct 3 ms 4956 KB Output is correct
9 Correct 12 ms 5336 KB Output is correct
10 Correct 36 ms 6600 KB Output is correct
11 Correct 178 ms 12368 KB Output is correct
12 Correct 89 ms 12112 KB Output is correct
13 Correct 160 ms 12620 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 8420 KB Output is correct
2 Correct 265 ms 18344 KB Output is correct
3 Correct 96 ms 15308 KB Output is correct
4 Correct 131 ms 9040 KB Output is correct
5 Correct 179 ms 9068 KB Output is correct
6 Correct 158 ms 9044 KB Output is correct
7 Correct 147 ms 8532 KB Output is correct
8 Correct 60 ms 8348 KB Output is correct
9 Correct 218 ms 18860 KB Output is correct
10 Correct 273 ms 18256 KB Output is correct
11 Correct 218 ms 18260 KB Output is correct
12 Correct 257 ms 17116 KB Output is correct
13 Correct 109 ms 19900 KB Output is correct
14 Correct 122 ms 15312 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 11860 KB Output is correct
2 Correct 276 ms 17672 KB Output is correct
3 Correct 167 ms 18512 KB Output is correct
4 Correct 149 ms 16212 KB Output is correct
5 Correct 177 ms 15600 KB Output is correct
6 Correct 166 ms 15696 KB Output is correct
7 Correct 211 ms 14928 KB Output is correct
8 Correct 166 ms 18512 KB Output is correct
9 Correct 227 ms 19160 KB Output is correct
10 Correct 290 ms 18668 KB Output is correct
11 Correct 280 ms 18676 KB Output is correct
12 Correct 288 ms 17604 KB Output is correct
13 Correct 286 ms 22352 KB Output is correct
14 Correct 230 ms 15564 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 19232 KB Output is correct
2 Correct 269 ms 17680 KB Output is correct
3 Correct 109 ms 21840 KB Output is correct
4 Correct 262 ms 19276 KB Output is correct
5 Correct 280 ms 18596 KB Output is correct
6 Correct 254 ms 18512 KB Output is correct
7 Correct 266 ms 17748 KB Output is correct
8 Correct 108 ms 21840 KB Output is correct
9 Correct 106 ms 15268 KB Output is correct