Submission #92033

#	Time	Username	Problem	Language	Result	Execution time	Memory
92033		ngot23	Ball Machine (BOI13_ballmachine)	C++11	100 / 100	235 ms	27504 KiB

ballmachine

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i=(a) ; i<=(b) ; ++i)
#define mp make_pair
#define pii pair<int, int>
#define PB push_back
#define F first
#define S second
#define Task "     12   toan    2          "
using namespace std;
const int N=100005;
int n, Q, root, par[N][20], mn[N], h[N], flag[N];
vector <int > g[N];

int cnt, b[N], dd[N];
priority_queue <int > q;

void setup() {
    cin >> n >> Q;
    rep(i, 1, n) {
        int u; cin >> u;
        if(u==0) root=i;
        else g[u].PB(i);
    }
}

void DFS(int u) {
    mn[u]=u;
    for(int v:g[u]) {
        par[v][0]=u;
        rep(i, 1, 16) par[v][i]=par[par[v][i-1]][i-1];
        h[v]=h[u]+1;
        DFS(v);
        mn[u]=min(mn[u], mn[v]);
    }
}

bool cmp(int u, int v) {
    return mn[u]<mn[v];
}

void xuli(int u) {
    sort(g[u].begin(), g[u].end(), cmp);
    for(int v:g[u]) xuli(v);
    b[++cnt]=u; flag[u]=cnt;
    q.push(-cnt);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen(Task".inp", "r", stdin);
    //freopen(Task".out", "w", stdout);
    setup();
    DFS(root);
    xuli(root);
    while(Q--) {
        int t, k;
        cin >> t >> k;
        if(t==1) {
            int id;
            while(k--) {
                id=-q.top(); q.pop();
                dd[b[id]]=1;
            }
            cout << b[id] << '\n';
        } else {
            int x=k;
            for(int i=17 ; i>=0 ; --i) {
                if(dd[par[x][i]]) {
                    x=par[x][i];
                }
            }
            cout << h[k]-h[x] << '\n';
            dd[x]=0;
            q.push(-flag[x]);
        }
    }
    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:59:17: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
             int id;
                 ^~

• Subtask 1: 25 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5