oj.uz

답안 #923798

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
923798 2024-02-07T19:18:52 Z n3rm1n Ball Machine (BOI13_ballmachine) C++17
100 / 100
 86 ms 24008 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN = 1e5 + 10, MAXLOG  = 22;
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], lvl[MAXN], cnt;
int sub[MAXN];
void dfs00(int beg, int h)
{
    sub[beg] = beg;
    lvl[beg] = h;
     int nb;
    for (int i = 0; i < g[beg].size(); ++ i)
    {
        nb = g[beg][i];
        dfs00(nb, h+1);
        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 jump[MAXN][MAXLOG];
void make_jumps()
{
    for (int i = 1; i <= n; ++ i)
        jump[i][0] = p[i];
    for (int j = 1; j <= 17; ++ j)
        for (int i = 1; i <= n; ++ i)
            jump[i][j] = jump[jump[i][j-1]][j-1];
}
int find_ans(int x)
{
    int newx = x;
    for (int j = 17; j >= 0; -- j)
    {
        int p = jump[x][j];
        if(p == 0)continue;
        if(used[p] == 1)x = p;
    }
    return x;
}
int main()
{
    speed();

    read();
    dfs00(root, 1);
    sort_g();
    dfs0(root);


    for (int i = 1; i <= n; ++ i)
        q.push(make_pair(-points[i], i));

    make_jumps();
    int t, x;
    while(que --)
    {
        cin >> t >> x;
        if(t == 1)
            cout << query_type1(x) << endl;
        else
        {
            int xx = x;
            x = find_ans(x);
            q.push(make_pair(-points[x], x));
            used[x] = 0;
            cout << lvl[xx] - lvl[x] << endl;
        }
    }
    return 0;
}

Compilation message

ballmachine.cpp: In function 'void dfs00(int, int)':
ballmachine.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int i = 0; i < g[beg].size(); ++ i)
      |                     ~~^~~~~~~~~~~~~~~
ballmachine.cpp: In function 'void dfs0(int)':
ballmachine.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for (int i = 0; i < g[beg].size(); ++ i)
      |                     ~~^~~~~~~~~~~~~~~
ballmachine.cpp: In function 'int find_ans(int)':
ballmachine.cpp:89:9: warning: unused variable 'newx' [-Wunused-variable]
   89 |     int newx = x;
      |         ^~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 52 ms 13008 KB Output is correct
3 Correct 33 ms 13064 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 4440 KB Output is correct
6 Correct 1 ms 4952 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct
9 Correct 4 ms 6748 KB Output is correct
10 Correct 11 ms 7352 KB Output is correct
11 Correct 50 ms 13000 KB Output is correct
12 Correct 41 ms 13244 KB Output is correct
13 Correct 48 ms 13000 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 9176 KB Output is correct
2 Correct 81 ms 19408 KB Output is correct
3 Correct 43 ms 15840 KB Output is correct
4 Correct 36 ms 10968 KB Output is correct
5 Correct 42 ms 10964 KB Output is correct
6 Correct 38 ms 10964 KB Output is correct
7 Correct 41 ms 10240 KB Output is correct
8 Correct 23 ms 9176 KB Output is correct
9 Correct 67 ms 19856 KB Output is correct
10 Correct 84 ms 19464 KB Output is correct
11 Correct 67 ms 19660 KB Output is correct
12 Correct 71 ms 17860 KB Output is correct
13 Correct 53 ms 22704 KB Output is correct
14 Correct 41 ms 15816 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 14544 KB Output is correct
2 Correct 75 ms 18124 KB Output is correct
3 Correct 57 ms 21712 KB Output is correct
4 Correct 54 ms 18632 KB Output is correct
5 Correct 67 ms 18140 KB Output is correct
6 Correct 57 ms 18244 KB Output is correct
7 Correct 50 ms 16848 KB Output is correct
8 Correct 56 ms 21708 KB Output is correct
9 Correct 83 ms 20032 KB Output is correct
10 Correct 85 ms 19660 KB Output is correct
11 Correct 79 ms 19588 KB Output is correct
12 Correct 74 ms 18140 KB Output is correct
13 Correct 86 ms 24004 KB Output is correct
14 Correct 63 ms 15824 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 20224 KB Output is correct
2 Correct 82 ms 18088 KB Output is correct
3 Correct 54 ms 24004 KB Output is correct
4 Correct 77 ms 20256 KB Output is correct
5 Correct 78 ms 19656 KB Output is correct
6 Correct 76 ms 19780 KB Output is correct
7 Correct 78 ms 18116 KB Output is correct
8 Correct 54 ms 24008 KB Output is correct
9 Correct 41 ms 15880 KB Output is correct