oj.uz

Submission #923772

# Submission time Handle Problem Language Result Execution time Memory
923772 2024-02-07T18:15:40 Z n3rm1n Ball Machine (BOI13_ballmachine) C++17
7.53968 / 100
 56 ms 12756 KB 
#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;
        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];
        if(!points[nb])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));
            cout << 0 << endl;
        }
    }
    return 0;
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3164 KB Output isn't correct
2 Incorrect 42 ms 5624 KB Output isn't correct
3 Incorrect 35 ms 5872 KB Output isn't correct
4 Incorrect 1 ms 3164 KB Output isn't correct
5 Incorrect 1 ms 3420 KB Output isn't correct
6 Incorrect 1 ms 3420 KB Output isn't correct
7 Incorrect 1 ms 3420 KB Output isn't correct
8 Incorrect 2 ms 3420 KB Output isn't correct
9 Incorrect 4 ms 3420 KB Output isn't correct
10 Incorrect 10 ms 3932 KB Output isn't correct
11 Incorrect 44 ms 5492 KB Output isn't correct
12 Incorrect 32 ms 5880 KB Output isn't correct
13 Incorrect 43 ms 5588 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 5336 KB Output is correct
2 Incorrect 51 ms 9276 KB Output isn't correct
3 Incorrect 31 ms 6600 KB Output isn't correct
4 Incorrect 27 ms 5588 KB Output isn't correct
5 Incorrect 27 ms 5308 KB Output isn't correct
6 Incorrect 26 ms 5332 KB Output isn't correct
7 Incorrect 26 ms 4832 KB Output isn't correct
8 Correct 18 ms 5336 KB Output is correct
9 Incorrect 46 ms 9804 KB Output isn't correct
10 Incorrect 49 ms 9340 KB Output isn't correct
11 Incorrect 51 ms 9248 KB Output isn't correct
12 Incorrect 56 ms 8148 KB Output isn't correct
13 Correct 36 ms 11800 KB Output is correct
14 Incorrect 32 ms 6596 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 6620 KB Output isn't correct
2 Incorrect 45 ms 8152 KB Output isn't correct
3 Incorrect 37 ms 10968 KB Output isn't correct
4 Incorrect 32 ms 8660 KB Output isn't correct
5 Incorrect 34 ms 8152 KB Output isn't correct
6 Incorrect 31 ms 8152 KB Output isn't correct
7 Incorrect 30 ms 7380 KB Output isn't correct
8 Incorrect 32 ms 10972 KB Output isn't correct
9 Incorrect 48 ms 9688 KB Output isn't correct
10 Incorrect 46 ms 9176 KB Output isn't correct
11 Incorrect 50 ms 9172 KB Output isn't correct
12 Incorrect 43 ms 8140 KB Output isn't correct
13 Incorrect 47 ms 12756 KB Output isn't correct
14 Incorrect 41 ms 6356 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 9796 KB Output isn't correct
2 Incorrect 47 ms 8144 KB Output isn't correct
3 Correct 38 ms 12756 KB Output is correct
4 Incorrect 51 ms 9688 KB Output isn't correct
5 Incorrect 46 ms 9180 KB Output isn't correct
6 Incorrect 45 ms 9284 KB Output isn't correct
7 Incorrect 46 ms 8164 KB Output isn't correct
8 Correct 43 ms 12752 KB Output is correct
9 Incorrect 29 ms 6604 KB Output isn't correct