oj.uz

Submission #989154

# Submission time Handle Problem Language Result Execution time Memory
989154 2024-05-27T15:48:34 Z SuPythony Ball Machine (BOI13_ballmachine) C++17
100 / 100
 342 ms 41556 KB 
#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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 275 ms 15952 KB Output is correct
3 Correct 172 ms 16212 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 15 ms 1404 KB Output is correct
10 Correct 42 ms 4188 KB Output is correct
11 Correct 238 ms 15836 KB Output is correct
12 Correct 174 ms 16100 KB Output is correct
13 Correct 210 ms 16208 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 7980 KB Output is correct
2 Correct 246 ms 32080 KB Output is correct
3 Correct 187 ms 23760 KB Output is correct
4 Correct 150 ms 10072 KB Output is correct
5 Correct 145 ms 9820 KB Output is correct
6 Correct 149 ms 10064 KB Output is correct
7 Correct 156 ms 8144 KB Output is correct
8 Correct 132 ms 8120 KB Output is correct
9 Correct 229 ms 32668 KB Output is correct
10 Correct 253 ms 32064 KB Output is correct
11 Correct 273 ms 32216 KB Output is correct
12 Correct 234 ms 27732 KB Output is correct
13 Correct 223 ms 36692 KB Output is correct
14 Correct 191 ms 23756 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 16468 KB Output is correct
2 Correct 284 ms 28580 KB Output is correct
3 Correct 181 ms 33076 KB Output is correct
4 Correct 176 ms 26148 KB Output is correct
5 Correct 178 ms 25940 KB Output is correct
6 Correct 168 ms 25936 KB Output is correct
7 Correct 205 ms 22688 KB Output is correct
8 Correct 215 ms 33100 KB Output is correct
9 Correct 286 ms 32848 KB Output is correct
10 Correct 307 ms 32428 KB Output is correct
11 Correct 319 ms 32340 KB Output is correct
12 Correct 325 ms 28500 KB Output is correct
13 Correct 342 ms 41556 KB Output is correct
14 Correct 263 ms 23828 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 32800 KB Output is correct
2 Correct 333 ms 28496 KB Output is correct
3 Correct 260 ms 41300 KB Output is correct
4 Correct 337 ms 32848 KB Output is correct
5 Correct 293 ms 32340 KB Output is correct
6 Correct 244 ms 32340 KB Output is correct
7 Correct 301 ms 28496 KB Output is correct
8 Correct 259 ms 41284 KB Output is correct
9 Correct 197 ms 23760 KB Output is correct