oj.uz

Submission #385630

# Submission time Handle Problem Language Result Execution time Memory
385630 2021-04-04T16:19:23 Z blue Ball Machine (BOI13_ballmachine) C++17
100 / 100
 570 ms 25836 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N;
int Q;
int r;

int anc[100001][19];
vector<int> children[100001];
vector<int> subtree(100001, 0);
vector<int> height(100001, 0);
vector<int> mindes(100001, 1e9);

vector<int> occ(100001, 0);
vector<int> occ_bit(100001, 0);
vector<int> order_ind(100001);
vector<int> order(1, 0);




void dfs1(int u)
{
    subtree[u] = 1;
    mindes[u] = u;

    for(int e = 1; e <= 18; e++) anc[u][e] = anc[ anc[u][e-1] ][e-1];

    for(int v: children[u])
    {
        height[v] = height[u] + 1;
        dfs1(v);
        subtree[u] += subtree[v];
        mindes[u] = min(mindes[u], mindes[v]);
    }
}





void dfs2(int u)
{
    for(int v: children[u]) dfs2(v);
    order_ind[u] = order.size();
    order.push_back(u);
}


int insert(int l, int r)
{
    if(l == r)
    {
        occ[ order[l] ] = 1;
        for(int i = l; i <= N; i += i&-i) occ_bit[i]++;
        return order[l];
    }

    int m = (l+r)/2;
    int s = 0;
    for(int i = m; i >= 1; i -= i&-i) s += occ_bit[i];
    if(s < m) return insert(l, m);
    else return insert(m+1, r);
}


int erase(int v)
{
    int a = v;
    for(int i = 18; i >= 0; i--)
    {
        if(occ[ anc[a][i] ]) a = anc[a][i];
    }

    occ[a] = 0;
    for(int i = order_ind[a]; i <= N; i += i&-i) occ_bit[i]--;

    return(height[v] - height[a]);
}


int main()
{
    cin >> N >> Q;

    anc[0][0] = 0;
    for(int i = 1; i <= N; i++)
    {
        cin >> anc[i][0];
        children[ anc[i][0] ].push_back(i);
        if(anc[i][0] == 0) r = i;
    }

    dfs1(r);

    for(int i = 1; i <= N; i++)
        sort(children[i].begin(), children[i].end(),
            [] (int x, int y)
            {
                return mindes[x] < mindes[y];
            }
        );

    dfs2(r);

    while(Q--)
    {
        int t;
        cin >> t;


        if(t == 1)
        {
            int x;
            cin >> x;

            for(int i = 1; i <= x-1; i++) insert(1, N);
            cout << insert(1, N) << '\n';
        }

        else
        {
            int v;
            cin >> v;
            cout << erase(v) << '\n';
        }
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5100 KB Output is correct
2 Correct 388 ms 12912 KB Output is correct
3 Correct 357 ms 12656 KB Output is correct
4 Correct 5 ms 4972 KB Output is correct
5 Correct 5 ms 5100 KB Output is correct
6 Correct 7 ms 5100 KB Output is correct
7 Correct 8 ms 5100 KB Output is correct
8 Correct 9 ms 5100 KB Output is correct
9 Correct 37 ms 5484 KB Output is correct
10 Correct 78 ms 6892 KB Output is correct
11 Correct 425 ms 12784 KB Output is correct
12 Correct 343 ms 12656 KB Output is correct
13 Correct 388 ms 12764 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 9452 KB Output is correct
2 Correct 489 ms 20336 KB Output is correct
3 Correct 367 ms 15588 KB Output is correct
4 Correct 304 ms 10348 KB Output is correct
5 Correct 300 ms 10348 KB Output is correct
6 Correct 305 ms 10220 KB Output is correct
7 Correct 297 ms 9324 KB Output is correct
8 Correct 248 ms 9452 KB Output is correct
9 Correct 467 ms 20836 KB Output is correct
10 Correct 490 ms 20480 KB Output is correct
11 Correct 464 ms 20604 KB Output is correct
12 Correct 510 ms 18164 KB Output is correct
13 Correct 401 ms 23272 KB Output is correct
14 Correct 362 ms 15588 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 13176 KB Output is correct
2 Correct 546 ms 18668 KB Output is correct
3 Correct 343 ms 21608 KB Output is correct
4 Correct 325 ms 17636 KB Output is correct
5 Correct 371 ms 17384 KB Output is correct
6 Correct 313 ms 17256 KB Output is correct
7 Correct 299 ms 15720 KB Output is correct
8 Correct 331 ms 21608 KB Output is correct
9 Correct 551 ms 20964 KB Output is correct
10 Correct 546 ms 20588 KB Output is correct
11 Correct 520 ms 20864 KB Output is correct
12 Correct 517 ms 18668 KB Output is correct
13 Correct 542 ms 25836 KB Output is correct
14 Correct 431 ms 15972 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 522 ms 21100 KB Output is correct
2 Correct 503 ms 18620 KB Output is correct
3 Correct 443 ms 25580 KB Output is correct
4 Correct 570 ms 21392 KB Output is correct
5 Correct 500 ms 20588 KB Output is correct
6 Correct 482 ms 20460 KB Output is correct
7 Correct 491 ms 18540 KB Output is correct
8 Correct 422 ms 25452 KB Output is correct
9 Correct 350 ms 15844 KB Output is correct