oj.uz

답안 #755478

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
755478 2023-06-10T07:11:01 Z The_Samurai Ball Machine (BOI13_ballmachine) C++17
100 / 100
 685 ms 29648 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> g, b_jump;
vector<int> par, way, pos, sub;
vector<bool> ball;

int jump(int u, int h) {
    if (u == -1) return 0;
    if (h == 0) return u;
    int x = 31 - __builtin_clz(h);
    return jump(b_jump[u][x], h - (1 << x));
}

void dfs1(int u) {
    sub[u] = u;
    for (int h = 0; (1 << h) <= way.size(); h++) {
        b_jump[u][h] = way[(int) way.size() - (1 << h)];
    }
    way.emplace_back(u);
    for (int v: g[u]) {
        dfs1(v);
        sub[u] = min(sub[u], sub[v]);
    }
    way.pop_back();
}

void dfs2(int u) {
    for (int v: g[u]) {
        dfs2(v);
    }
    way.emplace_back(u);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    int n, q, h = 0;
    cin >> n >> q;
    while ((1 << h) < n) h++;
    b_jump.assign(n + 1, vector<int>(h + 1, -1));
    g.assign(n + 1, {});
    par.assign(n + 1, 0);
    ball.assign(n + 1, false);
    sub.assign(n + 1, 0);
    pos.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> par[i];
        g[par[i]].emplace_back(i);
    }
    way.clear();
    dfs1(0);
    for (int i = 1; i <= n; i++) {
        sort(g[i].begin(), g[i].end(), [&](int u, int v) {
            return sub[u] < sub[v];
        });
    }
    way.clear();
    dfs2(0);
    set<pair<int, int>> emp;
    for (int i = 0; i < n; i++) {
        emp.insert({i, way[i]});
        pos[way[i]] = i;
    }

    while (q--) {
        int t, x;
        cin >> t >> x;
        if (t == 1) {
            int i = 0, last = 0;
            vector<pair<int, int>> del;
            for (auto it = emp.begin(); i < x; i++, it++) {
                last = (*it).second;
                ball[(*it).second] = true;
                del.push_back(*it);
            }
            for (auto it: del) {
                emp.erase(it);
            }
            cout << last << '\n';
        } else {
            int l = 0, r = n - 1, best = -1;
            while (l <= r) {
                int m = (l + r) >> 1;
                int u = jump(x, m);
                if (ball[u] and !ball[par[u]]) {
                    best = m;
                    break;
                }
                if (ball[par[u]]) {
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }
            assert(best >= 0);
            x = jump(x, best);
            ball[x] = false;
            emp.insert({pos[x], x});
            cout << best << '\n';
        }
    }

    return 0;
}

Compilation message

ballmachine.cpp: In function 'void dfs1(int)':
ballmachine.cpp:19:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (int h = 0; (1 << h) <= way.size(); h++) {
      |                     ~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 161 ms 14552 KB Output is correct
3 Correct 70 ms 13984 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 7 ms 1108 KB Output is correct
10 Correct 29 ms 3812 KB Output is correct
11 Correct 164 ms 14552 KB Output is correct
12 Correct 72 ms 14044 KB Output is correct
13 Correct 115 ms 13896 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 5644 KB Output is correct
2 Correct 535 ms 25300 KB Output is correct
3 Correct 88 ms 20620 KB Output is correct
4 Correct 129 ms 8112 KB Output is correct
5 Correct 184 ms 7936 KB Output is correct
6 Correct 170 ms 7684 KB Output is correct
7 Correct 158 ms 6868 KB Output is correct
8 Correct 52 ms 5836 KB Output is correct
9 Correct 378 ms 25560 KB Output is correct
10 Correct 595 ms 25320 KB Output is correct
11 Correct 344 ms 24576 KB Output is correct
12 Correct 442 ms 23240 KB Output is correct
13 Correct 147 ms 25536 KB Output is correct
14 Correct 91 ms 20548 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 128 ms 13004 KB Output is correct
2 Correct 645 ms 23792 KB Output is correct
3 Correct 267 ms 23588 KB Output is correct
4 Correct 255 ms 20488 KB Output is correct
5 Correct 400 ms 20172 KB Output is correct
6 Correct 328 ms 20104 KB Output is correct
7 Correct 385 ms 18916 KB Output is correct
8 Correct 317 ms 23628 KB Output is correct
9 Correct 345 ms 25740 KB Output is correct
10 Correct 586 ms 25336 KB Output is correct
11 Correct 540 ms 25252 KB Output is correct
12 Correct 537 ms 23700 KB Output is correct
13 Correct 685 ms 29648 KB Output is correct
14 Correct 157 ms 21548 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 475 ms 25940 KB Output is correct
2 Correct 602 ms 23744 KB Output is correct
3 Correct 179 ms 28956 KB Output is correct
4 Correct 431 ms 25892 KB Output is correct
5 Correct 684 ms 25308 KB Output is correct
6 Correct 384 ms 24576 KB Output is correct
7 Correct 460 ms 23788 KB Output is correct
8 Correct 175 ms 28800 KB Output is correct
9 Correct 92 ms 20644 KB Output is correct