oj.uz

Submission #989144

# Submission time Handle Problem Language Result Execution time Memory
989144 2024-05-27T15:37:04 Z SuPythony Ball Machine (BOI13_ballmachine) C++17
35.5128 / 100
 1000 ms 28108 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;
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);
    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;
        }
    }
    for (int i=1; i<=n; i++) {
        sort(al[i].begin(),al[i].end());
    }
    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;
            ball[x]=0;
            next_node.insert({order[x],x});
            cout<<0<<"\n";
        }
    }
    return 0;
}

Compilation message

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

Subtask #1
3.84615384615 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Execution timed out 1094 ms 7144 KB Time limit exceeded
3 Correct 166 ms 7452 KB Output is correct
4 Execution timed out 1036 ms 344 KB Time limit exceeded
5 Incorrect 1 ms 348 KB Output isn't correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Execution timed out 1099 ms 348 KB Time limit exceeded
8 Incorrect 2 ms 348 KB Output isn't correct
9 Execution timed out 1095 ms 604 KB Time limit exceeded
10 Execution timed out 1064 ms 2120 KB Time limit exceeded
11 Incorrect 189 ms 7128 KB Output isn't correct
12 Correct 161 ms 7512 KB Output is correct
13 Incorrect 181 ms 7128 KB Output isn't correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 5468 KB Output is correct
2 Correct 211 ms 18768 KB Output is correct
3 Correct 174 ms 10580 KB Output is correct
4 Correct 144 ms 6340 KB Output is correct
5 Correct 137 ms 6356 KB Output is correct
6 Correct 135 ms 5968 KB Output is correct
7 Correct 160 ms 4440 KB Output is correct
8 Correct 121 ms 5692 KB Output is correct
9 Correct 200 ms 19284 KB Output is correct
10 Correct 200 ms 18780 KB Output is correct
11 Correct 256 ms 18768 KB Output is correct
12 Correct 201 ms 14676 KB Output is correct
13 Correct 190 ms 24944 KB Output is correct
14 Correct 210 ms 10668 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 102 ms 9816 KB Output isn't correct
2 Incorrect 208 ms 14928 KB Output isn't correct
3 Incorrect 148 ms 22612 KB Output isn't correct
4 Incorrect 139 ms 15440 KB Output isn't correct
5 Incorrect 151 ms 15144 KB Output isn't correct
6 Incorrect 139 ms 15188 KB Output isn't correct
7 Incorrect 140 ms 11916 KB Output isn't correct
8 Incorrect 139 ms 22356 KB Output isn't correct
9 Incorrect 215 ms 19368 KB Output isn't correct
10 Incorrect 223 ms 19068 KB Output isn't correct
11 Incorrect 243 ms 18772 KB Output isn't correct
12 Incorrect 215 ms 14928 KB Output isn't correct
13 Incorrect 244 ms 28004 KB Output isn't correct
14 Incorrect 269 ms 10448 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 216 ms 19536 KB Output isn't correct
2 Incorrect 215 ms 14932 KB Output isn't correct
3 Correct 198 ms 28108 KB Output is correct
4 Incorrect 220 ms 19284 KB Output isn't correct
5 Incorrect 213 ms 18780 KB Output isn't correct
6 Incorrect 201 ms 19024 KB Output isn't correct
7 Incorrect 221 ms 14928 KB Output isn't correct
8 Correct 196 ms 27988 KB Output is correct
9 Correct 183 ms 10448 KB Output is correct