oj.uz

Submission #667113

# Submission time Handle Problem Language Result Execution time Memory
667113 2022-11-30T11:56:26 Z ThegeekKnight16 Ball Machine (BOI13_ballmachine) C++14
100 / 100
 510 ms 25984 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
vector<int> grafo[MAXN];
int Sub[MAXN];
int MinSub[MAXN];
int lift[MAXN][25];
int seg[4*MAXN], lz[4*MAXN];
int tin[MAXN], tout[MAXN];
int tmp = 0;
int nit[MAXN];

void dfs(int v)
{
    // tin[v] = ++tmp;
    Sub[v] = 1; MinSub[v] = v;
    for (auto viz : grafo[v])
    {
        dfs(viz);
        Sub[v] += Sub[viz];
        MinSub[v] = min(MinSub[v], MinSub[viz]);
    }
    // tout[v] = tmp;
}

void dfsTin(int v)
{
    for (auto viz : grafo[v]) dfsTin(viz);
    tin[v] = ++tmp; nit[tmp] = v;
}

bool cmp(int a, int b)
{
    return MinSub[a] < MinSub[b];
}

void refresh(int pos, int ini, int fim)
{
    if (lz[pos] == -1) return;
    seg[pos] = (fim - ini + 1) * lz[pos];

    if (ini != fim)
    {
        int e = 2*pos; int d = 2*pos + 1;
        lz[e] = lz[pos];
        lz[d] = lz[pos];
    }
    lz[pos] = -1;
}

void update(int pos, int ini, int fim, int p, int q, int val)
{
    refresh(pos, ini, fim);
    if (q < ini || p > fim) return;
    if (p <= ini && fim <= q)
    {
        lz[pos] = val;
        refresh(pos, ini, fim);
        return;
    }
    int m = (ini + fim) / 2;
    int e = 2*pos; int d = 2*pos + 1;
    update(e, ini,  m , p, q, val);
    update(d, m+1, fim, p, q, val);
    seg[pos] = seg[e] + seg[d];
}

int query(int pos, int ini, int fim, int p, int q)
{
    refresh(pos, ini, fim);
    if (q < ini || p > fim) return 0;
    if (p <= ini && fim <= q) return seg[pos];
    int m = (ini + fim) / 2;
    int e = 2*pos; int d = 2*pos + 1;
    return query(e, ini, m, p, q) + query(d, m+1, fim, p, q);
}

int bb(int pos, int ini, int fim)
{
    refresh(pos, ini, fim);
    if (ini == fim) return ini;
    int m = (ini + fim) / 2;
    int e = 2*pos; int d = 2*pos + 1;
    if ((m - ini + 1) > seg[e]) return bb(e, ini, m);
    else return bb(d, m+1, fim);
}

void build(int pos, int ini, int fim)
{
    seg[pos] = 0; lz[pos] = -1;
    if (ini == fim) return;
    int m = (ini + fim) / 2;
    int e = 2*pos; int d = 2*pos + 1;
    build(e, ini,  m );
    build(d, m+1, fim);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, Q;
    cin >> N >> Q;
    for (int i = 1; i <= N; i++)
    {
        cin >> lift[i][0];
        grafo[lift[i][0]].push_back(i);
    }
    dfs(0);
    // for (int i = 1; i <= N; i++) cerr << "BABA " << i << " " << tin[i] << " " << tout[i] << '\n';
    build(1, 1, N);
    for (int i = 1; i <= N; i++) sort(grafo[i].begin(), grafo[i].end(), cmp);
    dfsTin(0);
    for (int k = 1; k <= 20; k++)
    {
        for (int i = 1; i <= N; i++) lift[i][k] = lift[ lift[i][k-1] ][k-1];
    }

    while (Q--)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int K;
            cin >> K;
            int pos = 0;
            while (K--)
            {
                pos = bb(1, 1, N);
                update(1, 1, N, pos, pos, 1);
            }
            cout << nit[pos] << '\n';
        }
        else
        {
            int X;
            cin >> X;
            int resp = 0;
            for (int k = 20; k >= 0; k--)
            {
                int prox = lift[X][k];
                if (prox == 0) continue;
                // cerr << X << " " << prox << '\n';
                if (query(1, 1, N, tin[prox], tin[prox]))
                {
                    // cerr << lift[X][k] << " esta cheio, somando " << (1 << k) << '\n';
                    X = prox;
                    resp += (1 << k);
                }
            }
            update(1, 1, N, tin[X], tin[X], 0);
            cout << resp << '\n';
        }
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 178 ms 12364 KB Output is correct
3 Correct 86 ms 12644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 3 ms 2868 KB Output is correct
7 Correct 4 ms 2772 KB Output is correct
8 Correct 3 ms 2772 KB Output is correct
9 Correct 12 ms 3324 KB Output is correct
10 Correct 35 ms 5112 KB Output is correct
11 Correct 181 ms 12372 KB Output is correct
12 Correct 99 ms 12576 KB Output is correct
13 Correct 185 ms 12472 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 7200 KB Output is correct
2 Correct 466 ms 21344 KB Output is correct
3 Correct 103 ms 17604 KB Output is correct
4 Correct 189 ms 8436 KB Output is correct
5 Correct 256 ms 8248 KB Output is correct
6 Correct 278 ms 8280 KB Output is correct
7 Correct 235 ms 7488 KB Output is correct
8 Correct 110 ms 7184 KB Output is correct
9 Correct 409 ms 21752 KB Output is correct
10 Correct 467 ms 21332 KB Output is correct
11 Correct 406 ms 21272 KB Output is correct
12 Correct 404 ms 19388 KB Output is correct
13 Correct 214 ms 23428 KB Output is correct
14 Correct 117 ms 17608 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 12304 KB Output is correct
2 Correct 510 ms 19916 KB Output is correct
3 Correct 270 ms 21652 KB Output is correct
4 Correct 237 ms 18440 KB Output is correct
5 Correct 280 ms 18124 KB Output is correct
6 Correct 271 ms 18164 KB Output is correct
7 Correct 254 ms 16796 KB Output is correct
8 Correct 287 ms 21628 KB Output is correct
9 Correct 331 ms 21940 KB Output is correct
10 Correct 438 ms 21520 KB Output is correct
11 Correct 445 ms 21452 KB Output is correct
12 Correct 441 ms 20080 KB Output is correct
13 Correct 482 ms 25932 KB Output is correct
14 Correct 158 ms 17604 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 22160 KB Output is correct
2 Correct 425 ms 19828 KB Output is correct
3 Correct 220 ms 25868 KB Output is correct
4 Correct 445 ms 22040 KB Output is correct
5 Correct 461 ms 21484 KB Output is correct
6 Correct 442 ms 21512 KB Output is correct
7 Correct 413 ms 19836 KB Output is correct
8 Correct 221 ms 25984 KB Output is correct
9 Correct 104 ms 17680 KB Output is correct