제출 #666824

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
666824		ThegeekKnight16	Ball Machine (BOI13_ballmachine)	C++17	17.31 / 100	1100 ms	25492 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 QuantBolas[MAXN];
int lift[MAXN][25];
int seg[4*MAXN];
int tin[MAXN], tout[MAXN];
int tmp = 0;

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

int colocaBolas(int v, int& K)
{

    int last = v;
    for (auto viz : grafo[v])
    {
        if (K == 0) return last;
        last = colocaBolas(viz, K);
        QuantBolas[v] += QuantBolas[viz];
    }

    if (K > 0) {QuantBolas[v]++; K--; return v;}
    else return last;
}

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++) 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';
            // for (int i = 1; i <= N; i++) cerr << i << " " << QuantBolas[i] << '\n';
            // cerr << '\n';
        }
        else
        {
            int X;
            cin >> X;
            int resp = 0;
            for (int k = 20; k >= 0; k--)
            {
                // cerr << X << " " << lift[X][k] << '\n';
                if (lift[X][k] == 0) continue;
                if (QuantBolas[lift[X][k]] == Sub[lift[X][k]])
                {
                    // cerr << lift[X][k] << " esta cheio, somando " << (1 << k) << '\n';
                    X = lift[X][k];
                    resp += (1 << k);
                }
            }
            while (X != 0) {QuantBolas[X]--; X = lift[X][0];}
            cout << resp << '\n';
        }
    }
}

• Subtask 1: 9.615384615384615 / 25
• Subtask 2: 4.285714285714286 / 30
• Subtask 3: 2.857142857142857 / 40
• Subtask 4: 0.5555555555555556 / 5