oj.uz

답안 #872088

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
872088 2023-11-12T09:30:43 Z sleepntsheep Ball Machine (BOI13_ballmachine) C++17
0 / 100
 360 ms 11660 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 (m - 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 2396 KB Output isn't correct
2 Incorrect 72 ms 3992 KB Output isn't correct
3 Incorrect 68 ms 3920 KB Output isn't correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Incorrect 1 ms 2396 KB Output isn't correct
6 Incorrect 1 ms 2396 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 7 ms 2652 KB Output isn't correct
10 Incorrect 16 ms 2908 KB Output isn't correct
11 Incorrect 87 ms 4180 KB Output isn't correct
12 Incorrect 71 ms 3924 KB Output isn't correct
13 Incorrect 91 ms 4076 KB Output isn't correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 127 ms 4436 KB Output isn't correct
2 Incorrect 245 ms 8276 KB Output isn't correct
3 Incorrect 126 ms 4776 KB Output isn't correct
4 Incorrect 53 ms 4188 KB Output isn't correct
5 Incorrect 95 ms 4316 KB Output isn't correct
6 Incorrect 122 ms 4176 KB Output isn't correct
7 Incorrect 66 ms 3764 KB Output isn't correct
8 Incorrect 124 ms 4368 KB Output isn't correct
9 Incorrect 114 ms 8020 KB Output isn't correct
10 Incorrect 242 ms 8276 KB Output isn't correct
11 Incorrect 157 ms 7508 KB Output isn't correct
12 Incorrect 165 ms 6188 KB Output isn't correct
13 Incorrect 296 ms 10500 KB Output isn't correct
14 Incorrect 121 ms 4860 KB Output isn't correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 51 ms 5400 KB Output isn't correct
2 Incorrect 251 ms 6864 KB Output isn't correct
3 Incorrect 262 ms 9552 KB Output isn't correct
4 Incorrect 128 ms 6748 KB Output isn't correct
5 Incorrect 241 ms 6996 KB Output isn't correct
6 Incorrect 141 ms 6996 KB Output isn't correct
7 Incorrect 151 ms 5712 KB Output isn't correct
8 Incorrect 266 ms 9812 KB Output isn't correct
9 Incorrect 265 ms 8276 KB Output isn't correct
10 Incorrect 304 ms 8356 KB Output isn't correct
11 Incorrect 360 ms 8276 KB Output isn't correct
12 Incorrect 221 ms 6680 KB Output isn't correct
13 Incorrect 163 ms 11660 KB Output isn't correct
14 Incorrect 63 ms 4944 KB Output isn't correct

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 142 ms 8180 KB Output isn't correct
2 Incorrect 155 ms 6736 KB Output isn't correct
3 Incorrect 255 ms 11180 KB Output isn't correct
4 Incorrect 150 ms 8112 KB Output isn't correct
5 Incorrect 150 ms 8260 KB Output isn't correct
6 Incorrect 349 ms 8056 KB Output isn't correct
7 Incorrect 156 ms 6736 KB Output isn't correct
8 Incorrect 251 ms 11344 KB Output isn't correct
9 Incorrect 107 ms 4640 KB Output isn't correct