oj.uz

답안 #699750

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
699750 2023-02-17T22:00:59 Z finn__ Ball Machine (BOI13_ballmachine) C++17
66.2943 / 100
 170 ms 26964 KB 
#include <bits/stdc++.h>
using namespace std;

#define N 100000

vector<unsigned> g[N], anc[N];
unsigned min_child[N], postorder[N];
bitset<N> has_ball;

unsigned calc_min_child(unsigned u)
{
    min_child[u] = u;
    for (unsigned const &v : g[u])
        min_child[u] = min(min_child[u], calc_min_child(v));
    return min_child[u];
}

unsigned traverse(unsigned u, vector<unsigned> &path, unsigned i = 0)
{
    for (size_t j = 1; j <= path.size(); j <<= 1)
        anc[u].push_back(path[path.size() - j]);
    path.push_back(u);

    for (unsigned const &v : g[u])
        i = traverse(v, path, i);

    path.pop_back();
    postorder[u] = i++;
    return i;
}

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

    size_t n, q;
    cin >> n >> q;
    unsigned r;

    for (size_t i = 0; i < n; i++)
    {
        unsigned p;
        cin >> p;
        if (!p)
            r = i;
        else
            g[p - 1].push_back(i);
    }

    calc_min_child(r);
    for (size_t i = 0; i < n; i++)
        sort(g[i].begin(), g[i].end(), [&](unsigned a, unsigned b)
             { return min_child[a] < min_child[b]; });

    vector<unsigned> path;
    traverse(r, path);

    priority_queue<pair<unsigned, unsigned>> qu;
    for (unsigned i = 0; i < n; i++)
        qu.emplace(n - postorder[i], i);

    while (q--)
    {
        unsigned t, x;
        cin >> t >> x;

        if (t == 1)
        {
            for (size_t i = 0; i < x; i++)
            {
                if (i + 1 == x)
                    cout << qu.top().second + 1 << '\n';
                has_ball[qu.top().second] = 1;
                qu.pop();
            }
        }
        else
        {
            x--;
            unsigned h = 0;

            for (size_t i = anc[x].size() - 1; i < anc[x].size(); i--)
                if (has_ball[anc[x][i]])
                    x = anc[x][i], h += (1U << i);

            has_ball[x] = 0;
            qu.emplace(n - postorder[x], x);
            cout << h << '\n';
        }
    }
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:57:13: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   57 |     traverse(r, path);
      |     ~~~~~~~~^~~~~~~~~

Subtask #1
19.2307692308 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 71 ms 9436 KB Output is correct
3 Correct 48 ms 9616 KB Output is correct
4 Correct 4 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Incorrect 3 ms 5076 KB Output isn't correct
8 Correct 3 ms 5076 KB Output is correct
9 Incorrect 6 ms 5332 KB Output isn't correct
10 Incorrect 16 ms 6232 KB Output isn't correct
11 Correct 66 ms 9452 KB Output is correct
12 Correct 49 ms 9660 KB Output is correct
13 Correct 63 ms 9380 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 8892 KB Output is correct
2 Correct 108 ms 20060 KB Output is correct
3 Correct 55 ms 11360 KB Output is correct
4 Correct 43 ms 9080 KB Output is correct
5 Correct 47 ms 9672 KB Output is correct
6 Correct 47 ms 9632 KB Output is correct
7 Correct 44 ms 8784 KB Output is correct
8 Correct 36 ms 8884 KB Output is correct
9 Correct 100 ms 18292 KB Output is correct
10 Correct 127 ms 20140 KB Output is correct
11 Correct 109 ms 20104 KB Output is correct
12 Correct 117 ms 18052 KB Output is correct
13 Correct 94 ms 23836 KB Output is correct
14 Correct 57 ms 11388 KB Output is correct

Subtask #3
14.2857142857 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 59 ms 11688 KB Output isn't correct
2 Incorrect 141 ms 18368 KB Output isn't correct
3 Correct 113 ms 21704 KB Output is correct
4 Incorrect 78 ms 15692 KB Output isn't correct
5 Correct 84 ms 17348 KB Output is correct
6 Correct 101 ms 17352 KB Output is correct
7 Incorrect 94 ms 15884 KB Output isn't correct
8 Correct 104 ms 21796 KB Output is correct
9 Incorrect 116 ms 18180 KB Output isn't correct
10 Incorrect 139 ms 20236 KB Output isn't correct
11 Incorrect 130 ms 20224 KB Output isn't correct
12 Incorrect 124 ms 18376 KB Output isn't correct
13 Incorrect 170 ms 26964 KB Output isn't correct
14 Correct 104 ms 11448 KB Output is correct

Subtask #4
2.77777777778 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 122 ms 18356 KB Output isn't correct
2 Incorrect 128 ms 18468 KB Output isn't correct
3 Correct 108 ms 26860 KB Output is correct
4 Incorrect 117 ms 18332 KB Output isn't correct
5 Correct 127 ms 20300 KB Output is correct
6 Correct 105 ms 20164 KB Output is correct
7 Incorrect 118 ms 18404 KB Output isn't correct
8 Correct 103 ms 26860 KB Output is correct
9 Correct 66 ms 11412 KB Output is correct