oj.uz

답안 #493470

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
493470 2021-12-11T13:56:49 Z goodluck2020 Ball Machine (BOI13_ballmachine) C++14
100 / 100
 136 ms 23792 KB 
#include <bits/stdc++.h>
#define task "ballmachine"
#define sz(X) ((int)X.size())

using namespace std;
const int N = 1e5 + 5;
int n, q, Root, Min[N], Rank[N], Time, P[N][20], HasBall[N];
vector < int > V[N];
struct Data
{
    int id, rk;
};
struct cmp
{
    bool operator() (Data A, Data B)
    {
        return A.rk > B.rk;
    }
};
priority_queue < Data , vector < Data > , cmp > NoBall;
void dfs1(int u)
{
    Min[u] = u;
    for(int v : V[u])
    {
        dfs1(v);
        Min[u] = min(Min[u], Min[v]);
    }
    sort(V[u].begin(), V[u].end(),
         [](int x, int y)
         {
             return Min[x] < Min[y];
         });
}
void dfs2(int u)
{
    for(int i = 0; i < sz(V[u]); i++)
    {
        int v = V[u][i];
        dfs2(v);
    }
    Rank[u] = ++Time;
}
void Build()
{
    dfs1(Root);
    dfs2(Root);
    for(int i = 1; i < 20; i++)
        for(int j = 1; j <= n; j++)
        P[j][i] = P[P[j][i-1]][i-1];
    for(int i = 1; i <= n; i++) NoBall.push({i, Rank[i]});
}
int Solve1(int k)
{
    int res;
    while(k)
    {
        k--;
        res = NoBall.top().id;
        HasBall[res] = 1;
        NoBall.pop();
    }
    return res;
}
int Solve2(int k)
{
    int res = 0;
    for(int i = 19; i >= 0; i--)
        if(HasBall[P[k][i]]) k = P[k][i], res += 1 << i;
    HasBall[k] = 0;
    NoBall.push({k, Rank[k]});
    return res;
}
int main()
{
    if(fopen(task ".inp","r"))
    {
        freopen(task ".inp","r",stdin);
        freopen(task ".out","w",stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= n; i++)
    {
        int p;
        cin >> p;
        if(p == 0) Root = i;
        P[i][0] = p;
        V[p].push_back(i);
    }
    Build();
    while(q--)
    {
        int type, k;
        cin >> type >> k;
        if(type == 1) cout << Solve1(k) << '\n';
        else cout << Solve2(k) << '\n';
    }
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         freopen(task ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:79:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         freopen(task ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp: In function 'int Solve1(int)':
ballmachine.cpp:63:12: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   63 |     return res;
      |            ^~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 78 ms 11532 KB Output is correct
3 Correct 55 ms 11296 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2764 KB Output is correct
7 Correct 2 ms 2764 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 5 ms 3148 KB Output is correct
10 Correct 15 ms 4816 KB Output is correct
11 Correct 71 ms 11452 KB Output is correct
12 Correct 53 ms 11232 KB Output is correct
13 Correct 61 ms 11528 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 7032 KB Output is correct
2 Correct 98 ms 19068 KB Output is correct
3 Correct 68 ms 14776 KB Output is correct
4 Correct 39 ms 8284 KB Output is correct
5 Correct 44 ms 8160 KB Output is correct
6 Correct 39 ms 8128 KB Output is correct
7 Correct 43 ms 7368 KB Output is correct
8 Correct 30 ms 6944 KB Output is correct
9 Correct 90 ms 19572 KB Output is correct
10 Correct 128 ms 19120 KB Output is correct
11 Correct 88 ms 19140 KB Output is correct
12 Correct 94 ms 17292 KB Output is correct
13 Correct 75 ms 20828 KB Output is correct
14 Correct 68 ms 14780 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 11240 KB Output is correct
2 Correct 117 ms 17696 KB Output is correct
3 Correct 88 ms 19388 KB Output is correct
4 Correct 72 ms 16124 KB Output is correct
5 Correct 71 ms 15828 KB Output is correct
6 Correct 73 ms 15848 KB Output is correct
7 Correct 68 ms 14464 KB Output is correct
8 Correct 91 ms 19296 KB Output is correct
9 Correct 115 ms 19772 KB Output is correct
10 Correct 109 ms 19316 KB Output is correct
11 Correct 105 ms 19268 KB Output is correct
12 Correct 109 ms 17684 KB Output is correct
13 Correct 131 ms 23792 KB Output is correct
14 Correct 92 ms 15564 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 19884 KB Output is correct
2 Correct 131 ms 17740 KB Output is correct
3 Correct 94 ms 23044 KB Output is correct
4 Correct 122 ms 19948 KB Output is correct
5 Correct 126 ms 19376 KB Output is correct
6 Correct 84 ms 19188 KB Output is correct
7 Correct 113 ms 17716 KB Output is correct
8 Correct 80 ms 23084 KB Output is correct
9 Correct 64 ms 14776 KB Output is correct