제출 #667108

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
667108		ThegeekKnight16	Ball Machine (BOI13_ballmachine)	C++17	62.00 / 100	468 ms	25948 KiB

ballmachine

#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, int val)
{
    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] >= val) return bb(e, ini, m, val);
    else return bb(d, m+1, fim, val - ((m - ini + 1) - seg[d]));
}

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 id = bb(1, 1, N, K);
            update(1, 1, N, 1, id, 1);
            cout << nit[id] << '\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: 9.615384615384615 / 25
• Subtask 2: 10.714285714285714 / 30
• Subtask 3: 40 / 40
• Subtask 4: 1.6666666666666667 / 5