제출 #102324

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
102324		MoNsTeR_CuBe	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	503 ms	43396 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;

#define int long long

vector< vector<int> > Graph;

vector< vector< pair<int, int> > > minChildren;

const int INF = 1e15;

int dfs(int x, int last){
    int mini = INF;
    minChildren[x].clear();
    for(int a : Graph[x]){
        if(a == last) continue;
        int b = dfs(a,x);
        mini = min(mini, b);
        minChildren[x].push_back(make_pair(b, a));
    }
    if(!Graph[x].size()){
        return x;
    }
    //cout << "NODE " << x << ' ' << minChildren[x].size() << endl;
    sort(minChildren[x].begin(), minChildren[x].end());
    return min(x, mini);
}

vector< bool > isFull;

vector<int> priority;

priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > pq;

int curr = 0;

vector< int> depth;

void add(int node, int d){
    depth[node] = d;
    for(auto a : minChildren[node]){
        add(a.second,d+1);
    }
    priority[node] = curr++;
    pq.push(make_pair(priority[node], node));
}

vector< int > up;

int tot ;

vector< vector< int > > parents;

void calc(int n){
    for(int i = 1; i<=n; i++){
        parents[0][i] = up[i];
        if(parents[0][i] == 0) parents[0][i] = -1;
    }
    for(int i = 1; i < 20; i++){
        for(int j = 1; j <= n; j++){
            if(parents[i-1][j] != -1)
                parents[i][j] = parents[i-1][parents[i-1][j]];
            else parents[i][j] = -1;
        }
    }
}

int ans(int x){
    int s = depth[x];
    int b = x;
    for(int i = 19; i >= 0; i--){
        if(parents[i][x] != -1 && isFull[parents[i][x]]){
            x = parents[i][x];
        }
    }
    int ar = depth[x];
    int ans = s-ar;
    if(ans != 0){
        isFull[x] = false;
        pq.push({priority[x],x});
        isFull[b] = true;
    }else{
        pq.push({priority[b], b});
    }
    return ans;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    Graph.resize(n+1);
    int root;
    up.resize(n+1);
    priority.resize(n+1);
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        Graph[a].push_back(i+1);
        up[i+1] = a;
        if(a == 0) root = i+1;
    }

    minChildren.resize(n+1);
    depth.resize(n+1);
    dfs(root,-1);
    add(root,0);

    isFull.resize(n+1);

    parents.resize(20, vector<int>(n+1));

    calc(n);

    while(q--){
        int a;
        cin >> a;
        int b;
        cin >> b;
        if(a == 1){
            int last = 0;
            for(int i = 0; i < b; i++){
                last = pq.top().second;
                isFull[last] = true;
                pq.pop();
            }
            cout << last << endl;
        }else{
            isFull[b] = false;
            cout << ans(b) << endl;
        }
    }
}

컴파일 시 표준 에러 (stderr) 메시지

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:108:8: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
     add(root,0);
     ~~~^~~~~~~~

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