oj.uz

답안 #385518

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
385518 2021-04-04T14:18:08 Z b00n0rp Ball Machine (BOI13_ballmachine) C++17
100 / 100
 582 ms 35564 KB 
#include<bits/stdc++.h>
using namespace std;

int n,q;
int par[100005][21];
int st[100005],fin[100005],dep[100005];
vector<int> adj[100005],euler;
int bould[100005],mn[100005];
int root,tim = 0;

void pre_dfs(int u){
    mn[u] = u;
    vector<pair<int,int> > gg;
    for(auto v:adj[u]){
        pre_dfs(v);
        gg.push_back({mn[v],v});
        mn[u] = min(mn[u],mn[v]);
    }
    sort(gg.begin(),gg.end());
    adj[u].clear();
    for(auto x:gg){
        adj[u].push_back(x.second);
    }
}

void dfs(int u,int p,int d){
    st[u] = tim;
    dep[u] = d;
    for(auto v:adj[u]){
        if(v != p){
            dfs(v,u,d+1);
        }
    }
    fin[u] = tim++;
    // cout << u << " " << st[u] << " " << fin[u] << endl;
    euler.push_back(u);
}

signed main(){
    cin >> n >> q;
    for(int i = 1; i <= n; i ++){
        cin >> par[i][0];
        if(!par[i][0]){
            par[i][0] = i;
            root = i;
        }
        else{
            adj[par[i][0]].push_back(i);
        }
    }
    for(int j = 1; j <= 20; j ++){
        for(int i = 1; i <= n; i ++){
            par[i][j] = par[par[i][j-1]][j-1];
        }
    }
    pre_dfs(root);
    dfs(root,root,0);
    set<int> s;
    for(int i = 0; i < n; i ++) s.insert(i);
    for(int i = 0; i < q; i++){
        int t; cin >> t;
        if(t == 1){
            int x; cin >> x;
            for(int j = 0; j < x-1; j ++){
                bould[(*s.begin())] = 1;
                s.erase(s.begin());
            }
            bould[(*s.begin())] = 1;
            cout << euler[(*s.begin())] << "\n";
            s.erase(s.begin());
        }
        else{
            int u; cin >> u;
            int u0 = u;
            for(int j = 19; j >= 0; j --){
                if(bould[fin[par[u][j]]]){
                    u = par[u][j];
                }
            }
            bould[fin[u]] = 0;
            s.insert(fin[u]);
            cout << dep[u0]-dep[u] << "\n";
        }
    }
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2796 KB Output is correct
2 Correct 435 ms 15208 KB Output is correct
3 Correct 348 ms 15132 KB Output is correct
4 Correct 3 ms 2668 KB Output is correct
5 Correct 4 ms 2796 KB Output is correct
6 Correct 6 ms 2924 KB Output is correct
7 Correct 6 ms 2924 KB Output is correct
8 Correct 7 ms 2924 KB Output is correct
9 Correct 33 ms 3436 KB Output is correct
10 Correct 85 ms 5740 KB Output is correct
11 Correct 445 ms 14960 KB Output is correct
12 Correct 341 ms 14832 KB Output is correct
13 Correct 453 ms 15088 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 248 ms 9068 KB Output is correct
2 Correct 543 ms 27752 KB Output is correct
3 Correct 374 ms 20348 KB Output is correct
4 Correct 311 ms 10860 KB Output is correct
5 Correct 353 ms 10988 KB Output is correct
6 Correct 314 ms 10860 KB Output is correct
7 Correct 307 ms 9196 KB Output is correct
8 Correct 249 ms 9068 KB Output is correct
9 Correct 492 ms 28132 KB Output is correct
10 Correct 498 ms 27544 KB Output is correct
11 Correct 472 ms 27592 KB Output is correct
12 Correct 511 ms 23976 KB Output is correct
13 Correct 410 ms 31212 KB Output is correct
14 Correct 423 ms 20188 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 241 ms 15740 KB Output is correct
2 Correct 550 ms 25060 KB Output is correct
3 Correct 346 ms 28652 KB Output is correct
4 Correct 342 ms 23012 KB Output is correct
5 Correct 364 ms 22632 KB Output is correct
6 Correct 370 ms 22504 KB Output is correct
7 Correct 341 ms 20088 KB Output is correct
8 Correct 379 ms 28652 KB Output is correct
9 Correct 545 ms 28264 KB Output is correct
10 Correct 568 ms 27948 KB Output is correct
11 Correct 551 ms 27880 KB Output is correct
12 Correct 554 ms 24804 KB Output is correct
13 Correct 582 ms 35564 KB Output is correct
14 Correct 474 ms 21084 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 563 ms 28312 KB Output is correct
2 Correct 543 ms 24788 KB Output is correct
3 Correct 439 ms 34888 KB Output is correct
4 Correct 536 ms 28260 KB Output is correct
5 Correct 542 ms 27780 KB Output is correct
6 Correct 479 ms 27496 KB Output is correct
7 Correct 556 ms 24848 KB Output is correct
8 Correct 431 ms 34796 KB Output is correct
9 Correct 378 ms 20312 KB Output is correct