oj.uz

Submission #1015909

# Submission time Handle Problem Language Result Execution time Memory
1015909 2024-07-07T04:34:01 Z caterpillow Ball Machine (BOI13_ballmachine) C++17
7.53968 / 100
 1000 ms 17760 KB 
#include <bits/stdc++.h>

using namespace std;

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, jmp, par;
LazySeg seg;

void dfs(int u, int p = -1) {
    par[u] = p;
    for (int v : adj[u]) {
        depth[v] = depth[u] + 1;
        if (depth[u] + depth[jmp[jmp[u]]] == 2 * depth[jmp[u]]) jmp[v] = jmp[jmp[u]];
        else jmp[v] = u;
        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;  
    };
    while (par[u] != u && good(par[u])) {
        if (good(jmp[u])) u = jmp[u];
        else u = par[u];
    }
    return u;
}

main() {
    cin.tie(0)->sync_with_stdio(0);
    
    cin >> n >> q;
    depth = pri = rpri = jmp = par = vt<int>(n);
    int rt = -1;
    F0R (i, n) {
        int p; cin >> p;
        p--;
        if (p >= 0) {
            par[i] = p;
            adj[p].pb(i);
        } else {
            rt = i;
        }
    }
    seg.init();
    F0R (i, n) sort(all(adj[i]));
    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:136:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  136 | main() {
      | ^~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 4696 KB Time limit exceeded
2 Execution timed out 1049 ms 7768 KB Time limit exceeded
3 Incorrect 43 ms 8528 KB Output isn't correct
4 Incorrect 2 ms 4696 KB Output isn't correct
5 Execution timed out 1096 ms 4700 KB Time limit exceeded
6 Execution timed out 1070 ms 4700 KB Time limit exceeded
7 Execution timed out 1029 ms 4696 KB Time limit exceeded
8 Execution timed out 1050 ms 4700 KB Time limit exceeded
9 Execution timed out 1040 ms 4952 KB Time limit exceeded
10 Execution timed out 1012 ms 5636 KB Time limit exceeded
11 Execution timed out 1041 ms 7768 KB Time limit exceeded
12 Incorrect 38 ms 8528 KB Output isn't correct
13 Execution timed out 1086 ms 8016 KB Time limit exceeded

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 7516 KB Output is correct
2 Execution timed out 1074 ms 13260 KB Time limit exceeded
3 Incorrect 52 ms 9448 KB Output isn't correct
4 Execution timed out 1044 ms 7768 KB Time limit exceeded
5 Execution timed out 1071 ms 7260 KB Time limit exceeded
6 Incorrect 130 ms 7768 KB Output isn't correct
7 Execution timed out 1040 ms 7184 KB Time limit exceeded
8 Correct 31 ms 7516 KB Output is correct
9 Execution timed out 1034 ms 13420 KB Time limit exceeded
10 Execution timed out 1039 ms 13396 KB Time limit exceeded
11 Incorrect 144 ms 13396 KB Output isn't correct
12 Execution timed out 1047 ms 11088 KB Time limit exceeded
13 Correct 57 ms 16216 KB Output is correct
14 Incorrect 53 ms 9424 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1022 ms 9048 KB Time limit exceeded
2 Execution timed out 1059 ms 11100 KB Time limit exceeded
3 Execution timed out 1056 ms 14416 KB Time limit exceeded
4 Incorrect 164 ms 11860 KB Output isn't correct
5 Incorrect 158 ms 11604 KB Output isn't correct
6 Incorrect 141 ms 11604 KB Output isn't correct
7 Execution timed out 1066 ms 9816 KB Time limit exceeded
8 Execution timed out 1070 ms 14424 KB Time limit exceeded
9 Execution timed out 1036 ms 12880 KB Time limit exceeded
10 Execution timed out 1022 ms 12632 KB Time limit exceeded
11 Execution timed out 1022 ms 12636 KB Time limit exceeded
12 Execution timed out 1051 ms 11096 KB Time limit exceeded
13 Execution timed out 1057 ms 16832 KB Time limit exceeded
14 Incorrect 67 ms 9628 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1047 ms 12892 KB Time limit exceeded
2 Execution timed out 1025 ms 10832 KB Time limit exceeded
3 Correct 57 ms 17748 KB Output is correct
4 Execution timed out 1030 ms 12888 KB Time limit exceeded
5 Incorrect 230 ms 13396 KB Output isn't correct
6 Incorrect 160 ms 13392 KB Output isn't correct
7 Execution timed out 1027 ms 11100 KB Time limit exceeded
8 Correct 68 ms 17760 KB Output is correct
9 Incorrect 43 ms 9356 KB Output isn't correct