Submission #923798

#	Time	Username	Problem	Language	Result	Execution time	Memory
923798		n3rm1n	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	86 ms	24008 KiB

ballmachine

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN = 1e5 + 10, MAXLOG  = 22;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int n, que;
int p[MAXN], root;
vector < int > g[MAXN];

void read()
{
    cin >> n >> que;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> p[i];
        if(!p[i])root = i;
        else g[p[i]].push_back(i);
    }
}

int points[MAXN], lvl[MAXN], cnt;
int sub[MAXN];
void dfs00(int beg, int h)
{
    sub[beg] = beg;
    lvl[beg] = h;
     int nb;
    for (int i = 0; i < g[beg].size(); ++ i)
    {
        nb = g[beg][i];
        dfs00(nb, h+1);
        sub[beg] = min(sub[beg], sub[nb]);
    }
}

bool cmp(int a, int b)
{
    return (sub[a] < sub[b]);
}
void sort_g()
{
    for (int i = 1; i <= n; ++ i)
        sort(g[i].begin(), g[i].end(), cmp);
}
void dfs0(int beg)
{

    int nb;
    for (int i = 0; i < g[beg].size(); ++ i)
    {
        nb = g[beg][i];
        dfs0(nb);
    }
    cnt ++;
    points[beg] = cnt;
}

int used[MAXN];
priority_queue < pair < int, int > > q;
int query_type1(int x)
{
    int v = 0;
    while(x --)
    {
        v = q.top().second;
        //cout << v << endl;
        used[v] = 1;
        q.pop();
    }
    return v;
}

int jump[MAXN][MAXLOG];
void make_jumps()
{
    for (int i = 1; i <= n; ++ i)
        jump[i][0] = p[i];
    for (int j = 1; j <= 17; ++ j)
        for (int i = 1; i <= n; ++ i)
            jump[i][j] = jump[jump[i][j-1]][j-1];
}
int find_ans(int x)
{
    int newx = x;
    for (int j = 17; j >= 0; -- j)
    {
        int p = jump[x][j];
        if(p == 0)continue;
        if(used[p] == 1)x = p;
    }
    return x;
}
int main()
{
    speed();

    read();
    dfs00(root, 1);
    sort_g();
    dfs0(root);


    for (int i = 1; i <= n; ++ i)
        q.push(make_pair(-points[i], i));

    make_jumps();
    int t, x;
    while(que --)
    {
        cin >> t >> x;
        if(t == 1)
            cout << query_type1(x) << endl;
        else
        {
            int xx = x;
            x = find_ans(x);
            q.push(make_pair(-points[x], x));
            used[x] = 0;
            cout << lvl[xx] - lvl[x] << endl;
        }
    }
    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'void dfs00(int, int)':
ballmachine.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int i = 0; i < g[beg].size(); ++ i)
      |                     ~~^~~~~~~~~~~~~~~
ballmachine.cpp: In function 'void dfs0(int)':
ballmachine.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for (int i = 0; i < g[beg].size(); ++ i)
      |                     ~~^~~~~~~~~~~~~~~
ballmachine.cpp: In function 'int find_ans(int)':
ballmachine.cpp:89:9: warning: unused variable 'newx' [-Wunused-variable]
   89 |     int newx = x;
      |         ^~~~

• Subtask 1: 25 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5