Submission #834988

#	Time	Username	Problem	Language	Result	Execution time	Memory
834988		vjudge1	Ball Machine (BOI13_ballmachine)	C++17	25 / 100	1086 ms	13132 KiB

ballmachine

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
vector<vector<ll>>graf;
vector<ll>minkir, minkan, atas;
vector<bool>penuh;
int total, akh;
void dfs(ll x, ll akhir) {
    for(auto it:graf[x]) {
        if(it == akhir) continue;
        dfs(it,x);
    }
    if(graf[x].size()==false) {
        minkir[x] = 1e18;
        minkan[x] = 1e18;
        return;
    }
    minkir[x] = min(min(minkir[graf[x][0]], minkan[graf[x][0]]), graf[x][0]);
    minkan[x] = min(min(minkir[graf[x][1]], minkan[graf[x][1]]), graf[x][1]);
}
void tambah(ll x) {
    if(graf[x].size() == 0 || (penuh[graf[x][0]] && penuh[graf[x][1]])) {
        penuh[x] = true;
        akh = x;
        return;
    }
    if(penuh[graf[x][1]]) {
        tambah(graf[x][0]);
    } else 
    if(penuh[graf[x][0]]) {
        tambah(graf[x][1]);
    } else 
    if(minkir[x] < minkan[x]) {
        tambah(graf[x][0]);
    } else {
        tambah(graf[x][1]);
    }
}
void hoek(ll x, ll akhir) {
    if(x==0) return;
    if(akhir != -1) {
        if(penuh[akhir]==false && penuh[x]) {
            penuh[akhir] = true;
            penuh[x] = false;
            total++;
        }
    }
    hoek(atas[x], x);
}
int main() {
    ll N,Q,par;
    cin >> N >> Q;
    graf.resize(N+1);
    atas.resize(N+1);
    minkir.resize(N+1);
    minkan.resize(N+1);
    penuh.resize(N+1);
    int root;
    for(int i=1; i<=N; i++) {
        cin >> par;
        graf[par].pb(i);
        atas[i] = par;
        if(par == 0) root = i;
    }
    dfs(root,0);
    ll jenis, k;
    while(Q--) {
        cin >> jenis >> k;
        if(jenis==1) {
            for(int i=0; i<k; i++) {
                tambah(root);
            }
            cout << akh << endl;
        } else {
            penuh[k] = false;
            total = 0;
            hoek(k,-1);
            cout << total << endl;
        }
    } 
    return 0;
}

Compilation message (stderr)

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

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