oj.uz

답안 #872087

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
872087 2023-11-12T09:29:10 Z sleepntsheep Ball Machine (BOI13_ballmachine) C++17
0 / 100
 460 ms 11536 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; J[root] = root;
    memset(lz, -1, sizeof lz);
    dfs(root);
    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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Incorrect 90 ms 4180 KB Output isn't correct
3 Incorrect 71 ms 3780 KB Output isn't correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Incorrect 1 ms 2648 KB Output isn't correct
6 Incorrect 1 ms 2652 KB Output isn't correct
7 Incorrect 1 ms 2652 KB Output isn't correct
8 Incorrect 1 ms 2652 KB Output isn't correct
9 Incorrect 6 ms 2740 KB Output isn't correct
10 Incorrect 16 ms 2908 KB Output isn't correct
11 Incorrect 77 ms 4168 KB Output isn't correct
12 Incorrect 71 ms 3920 KB Output isn't correct
13 Incorrect 67 ms 3816 KB Output isn't correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 174 ms 4536 KB Output isn't correct
2 Incorrect 224 ms 8184 KB Output isn't correct
3 Incorrect 112 ms 4352 KB Output isn't correct
4 Incorrect 111 ms 4432 KB Output isn't correct
5 Incorrect 164 ms 4688 KB Output isn't correct
6 Incorrect 86 ms 4592 KB Output isn't correct
7 Incorrect 129 ms 3788 KB Output isn't correct
8 Incorrect 173 ms 4432 KB Output isn't correct
9 Incorrect 128 ms 8580 KB Output isn't correct
10 Incorrect 232 ms 8276 KB Output isn't correct
11 Incorrect 392 ms 8336 KB Output isn't correct
12 Incorrect 264 ms 6480 KB Output isn't correct
13 Incorrect 300 ms 10060 KB Output isn't correct
14 Incorrect 100 ms 4188 KB Output isn't correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 59 ms 5456 KB Output isn't correct
2 Incorrect 239 ms 6692 KB Output isn't correct
3 Incorrect 299 ms 9688 KB Output isn't correct
4 Incorrect 146 ms 6744 KB Output isn't correct
5 Incorrect 248 ms 7000 KB Output isn't correct
6 Incorrect 237 ms 6980 KB Output isn't correct
7 Incorrect 151 ms 5716 KB Output isn't correct
8 Incorrect 268 ms 9552 KB Output isn't correct
9 Incorrect 260 ms 8408 KB Output isn't correct
10 Incorrect 313 ms 8276 KB Output isn't correct
11 Incorrect 358 ms 8556 KB Output isn't correct
12 Incorrect 225 ms 6688 KB Output isn't correct
13 Incorrect 164 ms 11536 KB Output isn't correct
14 Incorrect 62 ms 4952 KB Output isn't correct

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 150 ms 8148 KB Output isn't correct
2 Incorrect 156 ms 6740 KB Output isn't correct
3 Incorrect 130 ms 10828 KB Output isn't correct
4 Incorrect 149 ms 8784 KB Output isn't correct
5 Incorrect 154 ms 8356 KB Output isn't correct
6 Incorrect 460 ms 8184 KB Output isn't correct
7 Incorrect 163 ms 7004 KB Output isn't correct
8 Incorrect 130 ms 10832 KB Output isn't correct
9 Incorrect 92 ms 4188 KB Output isn't correct