oj.uz

답안 #923783

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
923783 2024-02-07T18:35:11 Z n3rm1n Ball Machine (BOI13_ballmachine) C++17
7.53968 / 100
 54 ms 12920 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;
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

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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 3164 KB Output isn't correct
2 Incorrect 40 ms 5688 KB Output isn't correct
3 Incorrect 30 ms 5836 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 1 ms 3416 KB Output isn't correct
9 Incorrect 3 ms 3420 KB Output isn't correct
10 Incorrect 9 ms 4056 KB Output isn't correct
11 Incorrect 40 ms 5604 KB Output isn't correct
12 Incorrect 31 ms 5832 KB Output isn't correct
13 Incorrect 37 ms 5644 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 5336 KB Output is correct
2 Incorrect 50 ms 9180 KB Output isn't correct
3 Incorrect 32 ms 6692 KB Output isn't correct
4 Incorrect 30 ms 5348 KB Output isn't correct
5 Incorrect 26 ms 5320 KB Output isn't correct
6 Incorrect 26 ms 5336 KB Output isn't correct
7 Incorrect 28 ms 4828 KB Output isn't correct
8 Correct 17 ms 5336 KB Output is correct
9 Incorrect 43 ms 9688 KB Output isn't correct
10 Incorrect 48 ms 9332 KB Output isn't correct
11 Incorrect 45 ms 9276 KB Output isn't correct
12 Incorrect 45 ms 7916 KB Output isn't correct
13 Correct 38 ms 11736 KB Output is correct
14 Incorrect 31 ms 6604 KB Output isn't correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 22 ms 6748 KB Output isn't correct
2 Incorrect 48 ms 8140 KB Output isn't correct
3 Incorrect 34 ms 11012 KB Output isn't correct
4 Incorrect 31 ms 8660 KB Output isn't correct
5 Incorrect 31 ms 8152 KB Output isn't correct
6 Incorrect 32 ms 8152 KB Output isn't correct
7 Incorrect 38 ms 7384 KB Output isn't correct
8 Incorrect 34 ms 10972 KB Output isn't correct
9 Incorrect 45 ms 9684 KB Output isn't correct
10 Incorrect 45 ms 9176 KB Output isn't correct
11 Incorrect 45 ms 9172 KB Output isn't correct
12 Incorrect 45 ms 8152 KB Output isn't correct
13 Incorrect 53 ms 12752 KB Output isn't correct
14 Incorrect 39 ms 6352 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 50 ms 9688 KB Output isn't correct
2 Incorrect 51 ms 8184 KB Output isn't correct
3 Correct 38 ms 12764 KB Output is correct
4 Incorrect 54 ms 9932 KB Output isn't correct
5 Incorrect 54 ms 9180 KB Output isn't correct
6 Incorrect 48 ms 9264 KB Output isn't correct
7 Incorrect 46 ms 8148 KB Output isn't correct
8 Correct 39 ms 12920 KB Output is correct
9 Incorrect 30 ms 6604 KB Output isn't correct