oj.uz

답안 #923790

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
923790 2024-02-07T18:51:50 Z n3rm1n Ball Machine (BOI13_ballmachine) C++17
35.5128 / 100
 73 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], sub[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
3.84615384615 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 3672 KB Output isn't correct
2 Incorrect 41 ms 6104 KB Output isn't correct
3 Correct 30 ms 6100 KB Output is 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 3744 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 4444 KB Output isn't correct
11 Incorrect 41 ms 5948 KB Output isn't correct
12 Correct 30 ms 6088 KB Output is correct
13 Incorrect 37 ms 5976 KB Output isn't correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 6104 KB Output is correct
2 Correct 55 ms 10488 KB Output is correct
3 Correct 36 ms 6868 KB Output is correct
4 Correct 30 ms 6104 KB Output is correct
5 Correct 28 ms 5844 KB Output is correct
6 Correct 27 ms 5848 KB Output is correct
7 Correct 30 ms 5284 KB Output is correct
8 Correct 19 ms 6356 KB Output is correct
9 Correct 50 ms 10956 KB Output is correct
10 Correct 55 ms 10536 KB Output is correct
11 Correct 48 ms 10380 KB Output is correct
12 Correct 50 ms 8656 KB Output is correct
13 Correct 42 ms 13624 KB Output is correct
14 Correct 36 ms 6600 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 25 ms 7392 KB Output isn't correct
2 Incorrect 58 ms 8868 KB Output isn't correct
3 Incorrect 38 ms 12764 KB Output isn't correct
4 Incorrect 35 ms 9684 KB Output isn't correct
5 Incorrect 35 ms 9176 KB Output isn't correct
6 Incorrect 35 ms 9176 KB Output isn't correct
7 Incorrect 35 ms 7892 KB Output isn't correct
8 Incorrect 38 ms 12764 KB Output isn't correct
9 Incorrect 58 ms 11052 KB Output isn't correct
10 Incorrect 51 ms 10492 KB Output isn't correct
11 Incorrect 50 ms 10456 KB Output isn't correct
12 Incorrect 50 ms 8908 KB Output isn't correct
13 Incorrect 73 ms 14784 KB Output isn't correct
14 Incorrect 48 ms 7128 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 57 ms 10956 KB Output isn't correct
2 Incorrect 52 ms 8900 KB Output isn't correct
3 Correct 47 ms 14712 KB Output is correct
4 Incorrect 57 ms 10960 KB Output isn't correct
5 Incorrect 59 ms 10700 KB Output isn't correct
6 Incorrect 48 ms 10456 KB Output isn't correct
7 Incorrect 51 ms 8856 KB Output isn't correct
8 Correct 44 ms 14788 KB Output is correct
9 Correct 36 ms 6868 KB Output is correct