Submission #923788

#	Time	Username	Problem	Language	Result	Execution time	Memory
923788		n3rm1n	Ball Machine (BOI13_ballmachine)	C++17	7.54 / 100	61 ms	14788 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;
int sub[MAXN];
void dfs00(int beg)
{
    sub[beg] = beg;
     int nb;
    for (int i = 0; i < g[beg].size(); ++ i)
    {
        nb = g[beg][i];
        dfs00(nb);
        sub[beg] = min(sub[beg], 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());
}
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();
    dfs00(root);
    sort_g();
    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 dfs00(int)':
ballmachine.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 0; i < g[beg].size(); ++ i)
      |                     ~~^~~~~~~~~~~~~~~
ballmachine.cpp: In function 'void dfs0(int)':
ballmachine.cpp:53:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     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