Submission #989124

#	Time	Username	Problem	Language	Result	Execution time	Memory
989124		SuPythony	Ball Machine (BOI13_ballmachine)	C++17	3.85 / 100	1101 ms	17500 KiB

ballmachine

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

vector<vector<int>> al, ral;
vector<int> mn;
vector<int> ball;
int root;

void mndfs(int u) {
    mn[u]=u;
    for (int v: al[u]) {
        mndfs(v);
        mn[u]=min(mn[u],mn[v]);
    }
}

int add_ball() {
    int curr=root;
    while (true) {
        int n=-1;
        int cmn=1e9;
        for (int v: al[curr]) {
            if (mn[v]<cmn&&!ball[v]) {
                cmn=mn[v];
                n=v;
            }
        }
        if (n==-1) {
            ball[curr]=1;
            return curr;
        }
        curr=n;
    }
}

int main() {
    int n, q; cin>>n>>q;
    al.assign(n+1,vector<int>());
    ral.assign(n+1,vector<int>());
    mn.assign(n+1,1e9);
    ball.assign(n+1,0);
    for (int i=1; i<=n; i++) {
        int p; cin>>p;
        if (p==0) {
            root=i;
        } else {
            al[p].push_back(i);
            ral[i].push_back(p);
        }
    }
    mndfs(root);
    while (q--) {
        int t; cin>>t;
        if (t==1) {
            int k; cin>>k;
            int ans;
            for (int i=0; i<k; i++) {
                ans=add_ball();
            }
            cout<<ans<<"\n";
        } else {
            int x; cin>>x;
            ball[x]=0;
            cout<<0<<"\n";
        }
    }
    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:61:24: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   61 |             cout<<ans<<"\n";
      |                        ^~~~

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