oj.uz

Submission #666838

# Submission time Handle Problem Language Result Execution time Memory
666838 2022-11-29T19:22:03 Z pedroslrey Ball Machine (BOI13_ballmachine) C++17
100 / 100
 385 ms 23484 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 10;
const int MAXK = 20;

vector<int> graph[MAXN];
int dp[MAXN][MAXK], prof[MAXN], mn[MAXN], xs[MAXN], redro[MAXN];
vector<int> order;
int seg[4*MAXN];

void dfs1(int u) {
    mn[u] = u;
    for (int v: graph[u]) {
        dfs1(v);
        mn[u] = min(mn[u], mn[v]);
    }
}

void dfs2(int u) {
    sort(graph[u].begin(), graph[u].end(), [&](int a, int b) { return mn[a] < mn[b]; });
    for (int v: graph[u]) {
        prof[v] = prof[u] + 1;
        dp[v][0] = u;
        for (int k = 1; k < MAXK; ++k)
            dp[v][k] = dp[dp[v][k-1]][k-1];
        dfs2(v);
    }
    redro[u] = order.size();
    order.push_back(u);
}

void update(int pos, int ini, int fim, int idx, int x) {
    if (ini == fim) {
        seg[pos] = x;
        return;
    }

    int m = (ini + fim)/2;
    if (idx <= m) update(2*pos, ini, m, idx, x);
    else update(2*pos + 1, m + 1, fim, idx, x);

    seg[pos] = min(seg[2*pos], seg[2*pos + 1]);
}

int bsearch(int pos, int ini, int fim) {
    if (ini == fim) return ini;

    int m = (ini + fim)/2;
    if (!seg[2*pos]) return bsearch(2*pos, ini, m);
    return bsearch(2*pos + 1, m + 1, fim);
}

int main() {
    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;

        graph[x].push_back(i);
    }

    dfs1(0);
    dfs2(0);

    for (int qq = 0; qq < q; ++qq) {
        int t, x;
        cin >> t >> x;

        if (t == 1) {
            int pos;
            for (int i = 0; i < x; ++i) {
                pos = bsearch(1, 0, n);
                update(1, 0, n, pos, 1);
                xs[order[pos]] = 1;
            }
            cout << order[pos] << "\n";
        }
        else {
            int atual = x;
            for (int k = MAXK-1; k >= 0; --k)
                if (xs[dp[atual][k]]) atual = dp[atual][k];
            update(1, 0, n, redro[atual], 0);
            xs[atual] = 0;

            cout << prof[x] - prof[atual] << "\n";
        }
    }
}

Compilation message

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

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 260 ms 10940 KB Output is correct
3 Correct 251 ms 10404 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 4 ms 2772 KB Output is correct
8 Correct 4 ms 2772 KB Output is correct
9 Correct 18 ms 3156 KB Output is correct
10 Correct 51 ms 4732 KB Output is correct
11 Correct 269 ms 10840 KB Output is correct
12 Correct 221 ms 10328 KB Output is correct
13 Correct 245 ms 10512 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 6532 KB Output is correct
2 Correct 323 ms 18456 KB Output is correct
3 Correct 219 ms 13852 KB Output is correct
4 Correct 188 ms 7780 KB Output is correct
5 Correct 191 ms 7604 KB Output is correct
6 Correct 186 ms 7448 KB Output is correct
7 Correct 230 ms 6784 KB Output is correct
8 Correct 146 ms 6592 KB Output is correct
9 Correct 293 ms 18756 KB Output is correct
10 Correct 324 ms 18500 KB Output is correct
11 Correct 316 ms 18028 KB Output is correct
12 Correct 305 ms 16404 KB Output is correct
13 Correct 275 ms 19784 KB Output is correct
14 Correct 251 ms 13776 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 11184 KB Output is correct
2 Correct 338 ms 17480 KB Output is correct
3 Correct 231 ms 19224 KB Output is correct
4 Correct 212 ms 16052 KB Output is correct
5 Correct 217 ms 15680 KB Output is correct
6 Correct 218 ms 15704 KB Output is correct
7 Correct 211 ms 14372 KB Output is correct
8 Correct 217 ms 19252 KB Output is correct
9 Correct 326 ms 19424 KB Output is correct
10 Correct 331 ms 19140 KB Output is correct
11 Correct 342 ms 19016 KB Output is correct
12 Correct 328 ms 17448 KB Output is correct
13 Correct 343 ms 23484 KB Output is correct
14 Correct 304 ms 15284 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 19096 KB Output is correct
2 Correct 385 ms 17160 KB Output is correct
3 Correct 264 ms 21964 KB Output is correct
4 Correct 360 ms 19052 KB Output is correct
5 Correct 348 ms 18508 KB Output is correct
6 Correct 299 ms 18192 KB Output is correct
7 Correct 330 ms 17184 KB Output is correct
8 Correct 269 ms 22056 KB Output is correct
9 Correct 219 ms 13884 KB Output is correct