oj.uz

Submission #699738

# Submission time Handle Problem Language Result Execution time Memory
699738 2023-02-17T21:38:31 Z finn__ Ball Machine (BOI13_ballmachine) C++17
66.2943 / 100
 121 ms 53436 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;
    assert(traverse(r, path) == n);

    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--;
            assert(has_ball[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:20: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   57 |     assert(traverse(r, path) == n);
      |                    ^

Subtask #1
19.2307692308 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 63 ms 9400 KB Output is correct
3 Correct 48 ms 9568 KB Output is correct
4 Correct 2 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 4 ms 5076 KB Output is correct
9 Runtime error 9 ms 10580 KB Execution killed with signal 6
10 Runtime error 17 ms 12372 KB Execution killed with signal 6
11 Correct 70 ms 9356 KB Output is correct
12 Correct 49 ms 9540 KB Output is correct
13 Correct 59 ms 9432 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 8880 KB Output is correct
2 Correct 106 ms 20044 KB Output is correct
3 Correct 56 ms 11464 KB Output is correct
4 Correct 44 ms 9064 KB Output is correct
5 Correct 43 ms 9604 KB Output is correct
6 Correct 41 ms 9616 KB Output is correct
7 Correct 43 ms 8784 KB Output is correct
8 Correct 29 ms 8920 KB Output is correct
9 Correct 93 ms 18292 KB Output is correct
10 Correct 109 ms 20160 KB Output is correct
11 Correct 98 ms 20072 KB Output is correct
12 Correct 100 ms 17992 KB Output is correct
13 Correct 93 ms 23880 KB Output is correct
14 Correct 53 ms 11380 KB Output is correct

Subtask #3
14.2857142857 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 23240 KB Execution killed with signal 6
2 Runtime error 85 ms 36528 KB Execution killed with signal 6
3 Correct 98 ms 21772 KB Output is correct
4 Runtime error 59 ms 31016 KB Execution killed with signal 6
5 Correct 80 ms 17320 KB Output is correct
6 Correct 82 ms 17332 KB Output is correct
7 Runtime error 63 ms 31332 KB Execution killed with signal 6
8 Correct 98 ms 21700 KB Output is correct
9 Runtime error 76 ms 36048 KB Execution killed with signal 6
10 Runtime error 86 ms 40168 KB Execution killed with signal 6
11 Runtime error 101 ms 40260 KB Execution killed with signal 6
12 Runtime error 85 ms 36572 KB Execution killed with signal 6
13 Runtime error 101 ms 53436 KB Execution killed with signal 6
14 Correct 70 ms 11404 KB Output is correct

Subtask #4
2.77777777778 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 76 ms 36232 KB Execution killed with signal 6
2 Runtime error 78 ms 36544 KB Execution killed with signal 6
3 Correct 106 ms 26756 KB Output is correct
4 Runtime error 87 ms 36388 KB Execution killed with signal 6
5 Correct 121 ms 20308 KB Output is correct
6 Correct 104 ms 20164 KB Output is correct
7 Runtime error 81 ms 36520 KB Execution killed with signal 6
8 Correct 109 ms 26948 KB Output is correct
9 Correct 53 ms 11424 KB Output is correct