oj.uz

Submission #872084

# Submission time Handle Problem Language Result Execution time Memory
872084 2023-11-12T09:25:26 Z sleepntsheep Ball Machine (BOI13_ballmachine) C++17
0 / 100
 18 ms 8284 KB 
#include <iostream>
#include <bitset>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#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], alloc, ta[N], h[N], tin[N], rv[N], timer, t[N<<1];
char lz[N];
struct { int v, l; } g[N-1];

inline void link(int u, int v) {
    if (h[u]) g[++alloc] = {v, 0}, g[ta[u]].l = alloc, ta[u] = alloc;
    else g[++alloc] = {v, h[u]}, h[u] = ta[u] = alloc;
}

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);
}

int qry(int u) { return qry(tin[u], tin[u]); }

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

void dfs(int u)
{
    for (auto j = h[u]; j; j = g[j].l)
    {
        P[g[j].v] = u;
        if (L[u] - L[J[u]] == L[J[u]] - L[J[J[u]]]) J[g[j].v] = J[J[u]];
        else J[g[j].v] = u;
        L[g[j].v] = L[u] + 1;
        dfs(g[j].v);
    }
    rv[tin[u] = timer++] = u;
}

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

int main()
{
    ShinLena;
    cin >> n >> q;
    for (int i = 0; i < n; ++i) cin >> P[i], (P[i] ? link(P[i]-1, i) : void(root = i));
    P[root] = root;
    memset(lz, -1, sizeof lz);
    dfs(0);
    return 0;
    for (int t, k; q--;)
    {
        cin >> t >> k;
        if (t == 1)
        {
            int l = 0, r = n - 1;
            while (l <= r)
            {
                int m = (l+r)/2;
                if (qry(0, m) <= k) l = m + 1;
                else r = m - 1;
            }
            cout << rv[l-1] + 1 << '\n';
            update(0, l-1, 1);
        }
        else
        {
            int r = highest(k-1);
            update(tin[r], tin[r], 0);
            cout << L[k-1] - L[r] << '\n';
        }
    }

    return 0;
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Incorrect 8 ms 2952 KB Output isn't correct
3 Incorrect 5 ms 2908 KB Output isn't correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Incorrect 0 ms 2396 KB Output isn't correct
6 Incorrect 1 ms 2392 KB Output isn't correct
7 Incorrect 1 ms 2396 KB Output isn't correct
8 Incorrect 1 ms 2396 KB Output isn't correct
9 Incorrect 1 ms 2648 KB Output isn't correct
10 Incorrect 2 ms 2652 KB Output isn't correct
11 Incorrect 7 ms 2908 KB Output isn't correct
12 Incorrect 8 ms 2956 KB Output isn't correct
13 Incorrect 6 ms 2904 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3676 KB Output isn't correct
2 Incorrect 10 ms 4956 KB Output isn't correct
3 Incorrect 7 ms 3164 KB Output isn't correct
4 Incorrect 3 ms 2652 KB Output isn't correct
5 Incorrect 3 ms 2648 KB Output isn't correct
6 Incorrect 2 ms 2652 KB Output isn't correct
7 Incorrect 2 ms 2652 KB Output isn't correct
8 Incorrect 2 ms 3676 KB Output isn't correct
9 Incorrect 11 ms 6984 KB Output isn't correct
10 Incorrect 12 ms 4956 KB Output isn't correct
11 Incorrect 8 ms 3164 KB Output isn't correct
12 Incorrect 8 ms 3072 KB Output isn't correct
13 Incorrect 8 ms 4952 KB Output isn't correct
14 Incorrect 8 ms 3084 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4440 KB Output isn't correct
2 Incorrect 13 ms 4700 KB Output isn't correct
3 Incorrect 11 ms 4700 KB Output isn't correct
4 Incorrect 9 ms 2908 KB Output isn't correct
5 Incorrect 6 ms 2904 KB Output isn't correct
6 Incorrect 9 ms 3096 KB Output isn't correct
7 Incorrect 8 ms 4272 KB Output isn't correct
8 Incorrect 11 ms 4548 KB Output isn't correct
9 Incorrect 8 ms 3164 KB Output isn't correct
10 Incorrect 11 ms 3092 KB Output isn't correct
11 Incorrect 9 ms 4108 KB Output isn't correct
12 Incorrect 14 ms 4712 KB Output isn't correct
13 Incorrect 8 ms 4700 KB Output isn't correct
14 Incorrect 8 ms 3176 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 3164 KB Output isn't correct
2 Incorrect 10 ms 5212 KB Output isn't correct
3 Incorrect 12 ms 8280 KB Output isn't correct
4 Incorrect 11 ms 3164 KB Output isn't correct
5 Incorrect 7 ms 3164 KB Output isn't correct
6 Incorrect 16 ms 6236 KB Output isn't correct
7 Incorrect 10 ms 5208 KB Output isn't correct
8 Incorrect 18 ms 8284 KB Output isn't correct
9 Incorrect 7 ms 3164 KB Output isn't correct