Submission #989154

#	Time	Username	Problem	Language	Result	Execution time	Memory
989154		SuPythony	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	342 ms	41556 KiB

ballmachine

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

vector<vector<int>> al;
vector<int> par;
vector<int> mn;
vector<int> ball;
vector<int> order;
set<pair<int,int>> next_node;
vector<vector<int>> up;
int root,n;

void dfs(int u) {
    for (int v: al[u]) {
        dfs(v);
    }
    order[u]=next_node.size()+1;
    next_node.insert({order[u],u});
}

void mndfs(int u) {
    mn[u]=u;
    set<pair<int,int>> o;
    for (int v: al[u]) {
        mndfs(v);
        mn[u]=min(mn[u],mn[v]);
        o.insert({mn[v],v});
    }
    al[u].clear();
    for (auto i: o) {
        al[u].push_back(i.second);
    }
}

int add_ball() {
    auto b=*next_node.begin();
    next_node.erase(next_node.begin());
    ball[b.second]=1;
    return b.second;
}

int main() {
    int q; cin>>n>>q;
    al.assign(n+1,vector<int>());
    par.assign(n+1,-1);
    mn.assign(n+1,1e9);
    ball.assign(n+1,0);
    order.assign(n+1,0);
    up.assign(n+1,vector<int>(26,-1));
    for (int i=1; i<=n; i++) {
        int p; cin>>p;
        if (p==0) {
            root=i;
        } else {
            al[p].push_back(i);
            par[i]=p;
            up[i][0]=p;
        }
    }
    for (int e=1; e<25; e++) {
        for (int i=1; i<=n; i++) {
            if (up[i][e-1]==-1) {
                up[i][e]=-1;
                continue;
            }
            up[i][e]=up[up[i][e-1]][e-1];
        }
    }
    mndfs(root);
    dfs(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;
            int ans=0;
            for (int e=25; e>=0; e--) {
                if (up[x][e]!=-1&&ball[up[x][e]]) {
                    x=up[x][e];
                    ans+=(int)pow(2,e);
                }
            }
            next_node.insert({order[x],x});
            ball[x]=0;
            cout<<ans<<"\n";
        }
    }
    return 0;
}

Compilation message (stderr)

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

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