oj.uz

Submission #385925

# Submission time Handle Problem Language Result Execution time Memory
385925 2021-04-05T08:39:21 Z Aryan_Raina Ball Machine (BOI13_ballmachine) C++14
100 / 100
 346 ms 33892 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld long double
#define ar array

const int INF = 1e15;
const int MOD = 1e9+7;

const int MXN = 1e5+9;
int up[20][MXN], mn[MXN], dist[MXN], ind[MXN];
vector<int> order, g[MXN];
bool hasBoulder[MXN];

void get_dp(int u) {
    mn[u] = u;
    for (int v : g[u]) {
        dist[v] = dist[u] + 1;
        get_dp(v);
        mn[u] = min(mn[u], mn[v]);
    }
}

void get_order(int u) {
    sort(g[u].begin(), g[u].end(), [&](int i, int j) { return mn[i] < mn[j]; });
    for (int v : g[u]) get_order(v);
    ind[u] = order.size();
    order.push_back(u);
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, m, rt; cin>>n>>m;
    for (int i = 0; i < n; i++) {
        cin>>up[0][i]; up[0][i]--;
        if (up[0][i] >= 0) g[up[0][i]].push_back(i);
        else up[0][i] = rt = i;
    }

    for (int i = 1; i < 20; i++) {
        for (int j = 0; j < n; j++) {
            up[i][j] = up[i-1][up[i-1][j]];
        }
    }

    get_dp(rt);
    get_order(rt);

    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 0; i < n; i++) pq.push(i);
    while (m--) {
        int t, x, ans; cin>>t>>x;
        if (t == 1) {
            while (x--) {
                hasBoulder[order[pq.top()]] = 1;
                ans = order[pq.top()]; pq.pop();
            }
            cout<<ans+1<<"\n";
        } else {
            x--;
            ans = dist[x];
            for (int i = 19; i >= 0; i--) {
                if (hasBoulder[up[i][x]]) x = up[i][x];
            }
            hasBoulder[x] = 0;
            pq.push(ind[x]);
            cout<<ans - dist[x]<<"\n";
        }
    }
}

Compilation message

ballmachine.cpp: In function 'int32_t main()':
ballmachine.cpp:59:23: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |             cout<<ans+1<<"\n";
      |                       ^
ballmachine.cpp:48:14: warning: 'rt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   48 |     get_order(rt);
      |     ~~~~~~~~~^~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2796 KB Output is correct
2 Correct 284 ms 18192 KB Output is correct
3 Correct 65 ms 18152 KB Output is correct
4 Correct 2 ms 2796 KB Output is correct
5 Correct 3 ms 2796 KB Output is correct
6 Correct 3 ms 3072 KB Output is correct
7 Correct 4 ms 3052 KB Output is correct
8 Correct 4 ms 3052 KB Output is correct
9 Correct 11 ms 3820 KB Output is correct
10 Correct 33 ms 6636 KB Output is correct
11 Correct 271 ms 18280 KB Output is correct
12 Correct 67 ms 18152 KB Output is correct
13 Correct 197 ms 18152 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 9064 KB Output is correct
2 Correct 346 ms 29412 KB Output is correct
3 Correct 85 ms 25312 KB Output is correct
4 Correct 132 ms 11500 KB Output is correct
5 Correct 120 ms 11408 KB Output is correct
6 Correct 121 ms 11372 KB Output is correct
7 Correct 112 ms 10348 KB Output is correct
8 Correct 39 ms 9276 KB Output is correct
9 Correct 334 ms 29796 KB Output is correct
10 Correct 338 ms 29364 KB Output is correct
11 Correct 219 ms 29284 KB Output is correct
12 Correct 333 ms 27360 KB Output is correct
13 Correct 106 ms 29924 KB Output is correct
14 Correct 78 ms 25312 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 16488 KB Output is correct
2 Correct 330 ms 27884 KB Output is correct
3 Correct 190 ms 27644 KB Output is correct
4 Correct 187 ms 24548 KB Output is correct
5 Correct 203 ms 24160 KB Output is correct
6 Correct 207 ms 24160 KB Output is correct
7 Correct 197 ms 22880 KB Output is correct
8 Correct 202 ms 27500 KB Output is correct
9 Correct 315 ms 29932 KB Output is correct
10 Correct 331 ms 29520 KB Output is correct
11 Correct 319 ms 29412 KB Output is correct
12 Correct 324 ms 28140 KB Output is correct
13 Correct 328 ms 33892 KB Output is correct
14 Correct 293 ms 25700 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 30224 KB Output is correct
2 Correct 325 ms 27884 KB Output is correct
3 Correct 107 ms 33380 KB Output is correct
4 Correct 297 ms 29924 KB Output is correct
5 Correct 319 ms 29412 KB Output is correct
6 Correct 212 ms 29440 KB Output is correct
7 Correct 327 ms 27884 KB Output is correct
8 Correct 109 ms 33380 KB Output is correct
9 Correct 79 ms 25316 KB Output is correct