Submission #923783

#	Time	Username	Problem	Language	Result	Execution time	Memory
923783		n3rm1n	Ball Machine (BOI13_ballmachine)	C++17	7.54 / 100	54 ms	12920 KiB

ballmachine

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN = 1e5 + 10;
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], cnt;
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 main()
{
    speed();

    read();
    dfs0(root);


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


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

Compilation message (stderr)

ballmachine.cpp: In function 'void dfs0(int)':
ballmachine.cpp:31:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int i = 0; i < g[beg].size(); ++ i)
      |                     ~~^~~~~~~~~~~~~~~

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