oj.uz

Submission #989149

# Submission time Handle Problem Language Result Execution time Memory
989149 2024-05-27T15:42:36 Z SuPythony Ball Machine (BOI13_ballmachine) C++17
60.0794 / 100
 1000 ms 27984 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;
            int curr=x;
            int ans=0;
            while (par[curr]!=-1&&ball[par[curr]]) {
                curr=par[curr];
                ans++;
            }
            next_node.insert({order[curr],curr});
            ball[curr]=0;
            cout<<ans<<"\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
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 240 ms 7248 KB Output is correct
3 Correct 186 ms 7412 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 14 ms 864 KB Output is correct
10 Correct 58 ms 2372 KB Output is correct
11 Correct 247 ms 7148 KB Output is correct
12 Correct 163 ms 7408 KB Output is correct
13 Correct 218 ms 7268 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 5468 KB Output is correct
2 Correct 203 ms 18780 KB Output is correct
3 Correct 192 ms 10420 KB Output is correct
4 Correct 135 ms 5976 KB Output is correct
5 Correct 141 ms 5968 KB Output is correct
6 Correct 133 ms 5976 KB Output is correct
7 Correct 136 ms 4444 KB Output is correct
8 Correct 114 ms 5476 KB Output is correct
9 Correct 198 ms 19224 KB Output is correct
10 Correct 196 ms 18768 KB Output is correct
11 Correct 197 ms 18772 KB Output is correct
12 Correct 205 ms 14680 KB Output is correct
13 Correct 170 ms 24916 KB Output is correct
14 Correct 180 ms 10700 KB Output is correct

Subtask #3
2.85714285714 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1050 ms 10104 KB Time limit exceeded
2 Execution timed out 1041 ms 14904 KB Time limit exceeded
3 Execution timed out 1059 ms 22284 KB Time limit exceeded
4 Execution timed out 1026 ms 15740 KB Time limit exceeded
5 Execution timed out 1052 ms 15188 KB Time limit exceeded
6 Execution timed out 1056 ms 15408 KB Time limit exceeded
7 Execution timed out 1062 ms 12284 KB Time limit exceeded
8 Execution timed out 1099 ms 22612 KB Time limit exceeded
9 Execution timed out 1046 ms 19416 KB Time limit exceeded
10 Execution timed out 1045 ms 19028 KB Time limit exceeded
11 Execution timed out 1060 ms 18820 KB Time limit exceeded
12 Execution timed out 1081 ms 15172 KB Time limit exceeded
13 Execution timed out 1059 ms 27820 KB Time limit exceeded
14 Correct 218 ms 10448 KB Output is correct

Subtask #4
2.22222222222 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1020 ms 19124 KB Time limit exceeded
2 Execution timed out 1051 ms 14876 KB Time limit exceeded
3 Correct 195 ms 27984 KB Output is correct
4 Execution timed out 1083 ms 19268 KB Time limit exceeded
5 Execution timed out 1030 ms 18772 KB Time limit exceeded
6 Correct 323 ms 19112 KB Output is correct
7 Execution timed out 1074 ms 14932 KB Time limit exceeded
8 Correct 193 ms 27984 KB Output is correct
9 Correct 174 ms 10448 KB Output is correct