Submission #666866

#	Time	Username	Problem	Language	Result	Execution time	Memory
666866		ThegeekKnight16	Ball Machine (BOI13_ballmachine)	C++14	89.76 / 100	1093 ms	26292 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 = -1;

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;
}

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 colocaBolas(int v, int K, int N)
{
    if (v != 0 && (query(1, 1, N, tin[v], tout[v]) + K) == Sub[v])
    {
        update(1, 1, N, tin[v], tout[v], 1);
        return v;
    }


    for (auto viz : grafo[v])
    {
        int QuantViz = query(1, 1, N, tin[viz], tout[viz]);
        if ((Sub[viz] - QuantViz) >= K) return colocaBolas(viz, K, N);
        else
        {
            K -= (Sub[viz] - QuantViz);
            update(1, 1, N, tin[viz], tout[viz], 1);
        }
    }
    return -1;
}

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);

    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;
            cout << colocaBolas(0, K, N) << '\n';
            // for (int i = 1; i <= N; i++) cerr << i << " " << query(1, 1, N, tin[i], tout[i]) << '\n';
            // cerr << '\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 / 25
• Subtask 2: 21.428571428571427 / 30
• Subtask 3: 40 / 40
• Subtask 4: 3.3333333333333335 / 5