oj.uz

Submission #923789

# Submission time Handle Problem Language Result Execution time Memory
923789 2024-02-07T18:50:52 Z n3rm1n Ball Machine (BOI13_ballmachine) C++17
7.53968 / 100
 67 ms 14796 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(), 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 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 3676 KB Output isn't correct
2 Incorrect 42 ms 5948 KB Output isn't correct
3 Incorrect 31 ms 6092 KB Output isn't correct
4 Incorrect 1 ms 3676 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 1 ms 3676 KB Output isn't correct
8 Incorrect 2 ms 3676 KB Output isn't correct
9 Incorrect 4 ms 3932 KB Output isn't correct
10 Incorrect 10 ms 4460 KB Output isn't correct
11 Incorrect 41 ms 6092 KB Output isn't correct
12 Incorrect 31 ms 6084 KB Output isn't correct
13 Incorrect 41 ms 6092 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6088 KB Output is correct
2 Incorrect 55 ms 10448 KB Output isn't correct
3 Incorrect 44 ms 6956 KB Output isn't correct
4 Incorrect 28 ms 6104 KB Output isn't correct
5 Incorrect 28 ms 5844 KB Output isn't correct
6 Incorrect 27 ms 6076 KB Output isn't correct
7 Incorrect 27 ms 5272 KB Output isn't correct
8 Correct 19 ms 6104 KB Output is correct
9 Incorrect 51 ms 10888 KB Output isn't correct
10 Incorrect 55 ms 10448 KB Output isn't correct
11 Incorrect 64 ms 10408 KB Output isn't correct
12 Incorrect 51 ms 8656 KB Output isn't correct
13 Correct 44 ms 13524 KB Output is correct
14 Incorrect 39 ms 7120 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 7396 KB Output isn't correct
2 Incorrect 51 ms 8976 KB Output isn't correct
3 Incorrect 40 ms 12764 KB Output isn't correct
4 Incorrect 35 ms 9680 KB Output isn't correct
5 Incorrect 43 ms 9164 KB Output isn't correct
6 Incorrect 37 ms 9172 KB Output isn't correct
7 Incorrect 35 ms 7892 KB Output isn't correct
8 Incorrect 37 ms 13016 KB Output isn't correct
9 Incorrect 67 ms 11208 KB Output isn't correct
10 Incorrect 52 ms 10544 KB Output isn't correct
11 Incorrect 53 ms 10452 KB Output isn't correct
12 Incorrect 51 ms 8908 KB Output isn't correct
13 Incorrect 62 ms 14664 KB Output isn't correct
14 Incorrect 57 ms 6864 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 10960 KB Output isn't correct
2 Incorrect 50 ms 8932 KB Output isn't correct
3 Correct 47 ms 14796 KB Output is correct
4 Incorrect 56 ms 10956 KB Output isn't correct
5 Incorrect 53 ms 10504 KB Output isn't correct
6 Incorrect 52 ms 10452 KB Output isn't correct
7 Incorrect 51 ms 8904 KB Output isn't correct
8 Correct 54 ms 14720 KB Output is correct
9 Incorrect 41 ms 7108 KB Output isn't correct