oj.uz

Submission #872122

# Submission time Handle Problem Language Result Execution time Memory
872122 2023-11-12T10:41:57 Z sleepntsheep Ball Machine (BOI13_ballmachine) C++17
0 / 100
 437 ms 19280 KB 
#include <iostream>
#include <cassert>
#include <queue>
#include <bitset>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <functional>
#include <array>

using i64 = long long;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;

using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 100000

int root, n, q, L[N], J[N], P[N], tout[N], rv[N], timer, t[N<<1], low[N];
signed char lz[N<<1];
vector<int> g[N];

inline void push(int v, int l, int r)
{
    if (-1 == lz[v]) return;
    t[v] = lz[v] * (r-l+1);
    if (l != r) 
    {
        int m = (l+r)/2, vl=v+1, vr=v+(m-l+1)*2;
        lz[vl] = lz[vr] = lz[v];
    }
    lz[v] = -1;
}

int qry(int x, int y, int v = 0, int l = 0, int r = n - 1)
{
    push(v, l, r);
    if (y < l || r < x) return 0;
    if (x <= l && r <= y) return t[v];
    int m = (l+r)/2, vl =v + 1, vr=v+(m-l+1)*2;
    return qry(x, y, vl, l, m) + qry(x, y, vr, m+1, r);
}

void update(int x, int y, int k, int v = 0, int l = 0, int r = n - 1)
{
    push(v, l, r);
    if (y < l || r < x) return;
    if (x <= l && r <= y) {lz[v] = k; push(v, l, r); return; }
    int m = (l+r)/2, vl =v + 1, vr=v+(m-l+1)*2;
    update(x, y, k, vl, l, m), update(x, y, k, vr, m+1, r);
    t[v] = t[vl] + t[vr];
}

inline int highest(int u)
{
    for (; u != P[u]; )
    {
        if (qry(tout[J[u]], tout[J[u]])) u = J[u];
        else if (qry(tout[P[u]], tout[P[u]])) u = P[u];
        else break;
    }
    return u;
}

void dfs(int u)
{
    for (auto v : g[u])
    {
        P[v] = u;
        J[v] = (L[u] - L[J[u]] == L[J[u]] - L[J[J[u]]]) ? J[J[u]] : u;
        L[v] = L[u] + 1;
        dfs(v);
    }
    rv[tout[u] = timer++] = u;
}

void init()
{
    ShinLena;
    cin >> n >> q;
    for (int i = 0; i < n; ++i) cin >> P[i], (P[i] ? void(g[P[i]-1].push_back(i)) : void(root = i));

    function<void(int)> dfs0 = [&](int u)
    {
        low[u] = u;
        for (auto v : g[u]) dfs0(v), low[u] = min(low[u], low[v]);
    };
    dfs0(root);

    for (int i = 0; i < n; ++i) sort(ALL(g[i]), [](int a, int b){ return low[a]<low[b]; });

    dfs(P[root] = J[root] = root);
    assert(timer == n);

    memset(lz, -1, sizeof lz);
}

void answer()
{
    for (int l, r, t, k; q--;)
    {
        cin >> t >> k;
        if (t == 1)
        {
            for (l = 0, r = n - 1; l <= r; )
            {
                int m = (l+r)/2;
                if (m - qry(0, m) <= k) l = m + 1;
                else r = m - 1;
            }
            update(0, l-1, 1);
            cout << rv[l-1] + 1 << '\n';
        }
        else
        {
            r = highest(k-1);
            update(tout[r], tout[r], 0);
            cout << L[k-1] - L[r] << '\n';
        }
    }
}

int main()
{
    init();
    answer();

    return 0;
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4700 KB Output isn't correct
2 Incorrect 92 ms 6696 KB Output isn't correct
3 Incorrect 127 ms 7000 KB Output isn't correct
4 Incorrect 1 ms 4700 KB Output isn't correct
5 Incorrect 1 ms 4700 KB Output isn't correct
6 Incorrect 1 ms 4700 KB Output isn't correct
7 Incorrect 2 ms 4700 KB Output isn't correct
8 Incorrect 2 ms 4700 KB Output isn't correct
9 Incorrect 6 ms 4700 KB Output isn't correct
10 Incorrect 18 ms 5232 KB Output isn't correct
11 Incorrect 90 ms 6740 KB Output isn't correct
12 Incorrect 125 ms 6924 KB Output isn't correct
13 Incorrect 97 ms 6812 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 129 ms 7576 KB Output isn't correct
2 Incorrect 113 ms 13004 KB Output isn't correct
3 Incorrect 154 ms 7756 KB Output isn't correct
4 Incorrect 52 ms 7260 KB Output isn't correct
5 Incorrect 55 ms 7000 KB Output isn't correct
6 Incorrect 69 ms 7000 KB Output isn't correct
7 Incorrect 54 ms 6328 KB Output isn't correct
8 Incorrect 132 ms 7572 KB Output isn't correct
9 Incorrect 94 ms 13228 KB Output isn't correct
10 Incorrect 96 ms 12784 KB Output isn't correct
11 Incorrect 163 ms 12928 KB Output isn't correct
12 Incorrect 85 ms 10324 KB Output isn't correct
13 Incorrect 319 ms 17492 KB Output isn't correct
14 Incorrect 173 ms 7632 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 114 ms 9040 KB Output isn't correct
2 Incorrect 246 ms 10688 KB Output isn't correct
3 Incorrect 265 ms 16092 KB Output isn't correct
4 Incorrect 180 ms 11496 KB Output isn't correct
5 Incorrect 147 ms 11344 KB Output isn't correct
6 Incorrect 150 ms 11352 KB Output isn't correct
7 Incorrect 140 ms 9280 KB Output isn't correct
8 Incorrect 251 ms 15952 KB Output isn't correct
9 Incorrect 266 ms 13512 KB Output isn't correct
10 Incorrect 259 ms 13136 KB Output isn't correct
11 Incorrect 260 ms 13284 KB Output isn't correct
12 Incorrect 247 ms 10684 KB Output isn't correct
13 Incorrect 437 ms 19280 KB Output isn't correct
14 Incorrect 83 ms 7628 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 339 ms 13648 KB Output isn't correct
2 Incorrect 245 ms 10936 KB Output isn't correct
3 Incorrect 330 ms 19188 KB Output isn't correct
4 Incorrect 350 ms 13504 KB Output isn't correct
5 Incorrect 251 ms 13108 KB Output isn't correct
6 Incorrect 197 ms 12884 KB Output isn't correct
7 Incorrect 241 ms 10592 KB Output isn't correct
8 Incorrect 323 ms 19024 KB Output isn't correct
9 Incorrect 132 ms 8140 KB Output isn't correct