oj.uz

Submission #923788

# Submission time Handle Problem Language Result Execution time Memory
923788 2024-02-07T18:50:19 Z n3rm1n Ball Machine (BOI13_ballmachine) C++17
7.53968 / 100
 61 ms 14788 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;
        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

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

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3672 KB Output isn't correct
2 Incorrect 42 ms 6092 KB Output isn't correct
3 Incorrect 32 ms 6208 KB Output isn't correct
4 Incorrect 1 ms 3672 KB Output isn't correct
5 Incorrect 1 ms 3676 KB Output isn't correct
6 Incorrect 1 ms 3676 KB Output isn't correct
7 Incorrect 2 ms 3672 KB Output isn't correct
8 Incorrect 2 ms 3676 KB Output isn't correct
9 Incorrect 3 ms 3932 KB Output isn't correct
10 Incorrect 10 ms 4444 KB Output isn't correct
11 Incorrect 47 ms 6088 KB Output isn't correct
12 Incorrect 32 ms 6088 KB Output isn't correct
13 Incorrect 38 ms 6100 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 6048 KB Output is correct
2 Incorrect 57 ms 10444 KB Output isn't correct
3 Incorrect 35 ms 7108 KB Output isn't correct
4 Incorrect 27 ms 6104 KB Output isn't correct
5 Incorrect 32 ms 6032 KB Output isn't correct
6 Incorrect 33 ms 6076 KB Output isn't correct
7 Incorrect 27 ms 5296 KB Output isn't correct
8 Correct 18 ms 6104 KB Output is correct
9 Incorrect 49 ms 10956 KB Output isn't correct
10 Incorrect 58 ms 10440 KB Output isn't correct
11 Incorrect 54 ms 10448 KB Output isn't correct
12 Incorrect 50 ms 8652 KB Output isn't correct
13 Correct 40 ms 13524 KB Output is correct
14 Incorrect 34 ms 7104 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 7504 KB Output isn't correct
2 Incorrect 50 ms 8912 KB Output isn't correct
3 Incorrect 37 ms 12764 KB Output isn't correct
4 Incorrect 38 ms 9680 KB Output isn't correct
5 Incorrect 41 ms 9168 KB Output isn't correct
6 Incorrect 35 ms 9116 KB Output isn't correct
7 Incorrect 44 ms 7892 KB Output isn't correct
8 Incorrect 37 ms 12752 KB Output isn't correct
9 Incorrect 60 ms 10956 KB Output isn't correct
10 Incorrect 52 ms 10452 KB Output isn't correct
11 Incorrect 53 ms 10456 KB Output isn't correct
12 Incorrect 48 ms 8916 KB Output isn't correct
13 Incorrect 54 ms 14672 KB Output isn't correct
14 Incorrect 54 ms 6872 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 10920 KB Output isn't correct
2 Incorrect 58 ms 8904 KB Output isn't correct
3 Correct 46 ms 14708 KB Output is correct
4 Incorrect 55 ms 10960 KB Output isn't correct
5 Incorrect 55 ms 10444 KB Output isn't correct
6 Incorrect 56 ms 10488 KB Output isn't correct
7 Incorrect 50 ms 8832 KB Output isn't correct
8 Correct 47 ms 14788 KB Output is correct
9 Incorrect 32 ms 6864 KB Output isn't correct