oj.uz

답안 #872090

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
872090 2023-11-12T09:31:54 Z sleepntsheep Ball Machine (BOI13_ballmachine) C++17
7.53968 / 100
 355 ms 11600 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 + 1 - 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 2 ms 2392 KB Output isn't correct
2 Incorrect 72 ms 4188 KB Output isn't correct
3 Incorrect 73 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 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 3008 KB Output isn't correct
11 Incorrect 97 ms 4156 KB Output isn't correct
12 Incorrect 69 ms 3980 KB Output isn't correct
13 Incorrect 79 ms 4204 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 4180 KB Output is correct
2 Incorrect 247 ms 8328 KB Output isn't correct
3 Incorrect 117 ms 4516 KB Output isn't correct
4 Incorrect 53 ms 4188 KB Output isn't correct
5 Incorrect 95 ms 4448 KB Output isn't correct
6 Incorrect 122 ms 4256 KB Output isn't correct
7 Incorrect 73 ms 3676 KB Output isn't correct
8 Correct 67 ms 4188 KB Output is correct
9 Incorrect 115 ms 7996 KB Output isn't correct
10 Incorrect 238 ms 8348 KB Output isn't correct
11 Incorrect 144 ms 7452 KB Output isn't correct
12 Incorrect 164 ms 6144 KB Output isn't correct
13 Correct 110 ms 9552 KB Output is correct
14 Incorrect 143 ms 4692 KB Output isn't correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 56 ms 5464 KB Output isn't correct
2 Incorrect 220 ms 6688 KB Output isn't correct
3 Incorrect 274 ms 9592 KB Output isn't correct
4 Incorrect 128 ms 6840 KB Output isn't correct
5 Incorrect 241 ms 6996 KB Output isn't correct
6 Incorrect 142 ms 6840 KB Output isn't correct
7 Incorrect 155 ms 6000 KB Output isn't correct
8 Incorrect 266 ms 9716 KB Output isn't correct
9 Incorrect 247 ms 8284 KB Output isn't correct
10 Incorrect 316 ms 8544 KB Output isn't correct
11 Incorrect 355 ms 8272 KB Output isn't correct
12 Incorrect 228 ms 6732 KB Output isn't correct
13 Incorrect 175 ms 11600 KB Output isn't correct
14 Incorrect 63 ms 4896 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 142 ms 8196 KB Output isn't correct
2 Incorrect 162 ms 6784 KB Output isn't correct
3 Correct 100 ms 10632 KB Output is correct
4 Incorrect 145 ms 8264 KB Output isn't correct
5 Incorrect 161 ms 8308 KB Output isn't correct
6 Incorrect 341 ms 8272 KB Output isn't correct
7 Incorrect 155 ms 6736 KB Output isn't correct
8 Correct 100 ms 10516 KB Output is correct
9 Incorrect 113 ms 4384 KB Output isn't correct