oj.uz

답안 #971237

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
971237 2024-04-28T08:14:24 Z makanhulia Ball Machine (BOI13_ballmachine) C++17
16.1111 / 100
 147 ms 24776 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5;
const int LOG = 18;
vector<int>adj[N + 2];
bool mark[N + 2];
int n, q, root;
int p[N + 2], mini[N + 2], in[N + 2], depth[N + 2], t[N + 2];
int up[N + 2][LOG];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
int timer = 1;

bool byMin(int &a, int &b){
    return mini[a] < mini[b];
}

void dfs(int cur, int d){
    depth[cur] = d;
    up[cur][0] = p[cur];
    for(int i = 1; i < LOG; i++){
        up[cur][i] = up[up[cur][i - 1]][i - 1];
    }

    for(auto &nxt: adj[cur]){
        dfs(nxt, d + 1);
    }

    t[cur] = timer;
    pq.emplace(timer++, cur);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;

    for(int i = 1; i <= n; i++){
        cin >> p[i];
        if(p[i] == 0) root = i;
        adj[p[i]].push_back(i);
        in[p[i]]++;
    }

    queue<int>leaf;
    for(int i = 1; i <= n; i++){
        if(in[p[i]]) continue;
        mini[i] = i;

        leaf.push(i);
    }

    while(!leaf.empty()){
        int cur = leaf.front(); leaf.pop();
        int nxt = p[cur];
        mini[nxt] = min(cur, nxt);
        in[nxt]--;
        if(!in[nxt]) leaf.push(nxt);
    }

    for(int i = 1; i <= n; i++){
        if(!adj[i].empty()) sort(adj[i].begin(), adj[i].end(), byMin);
    }

    dfs(root, 0);

    while(q--){
        int a, x; cin >> a >> x;
        if(a == 1){
            for(int i = 0; i < x; i++){
                if(i + 1 == x) cout << pq.top().second << '\n';
                mark[pq.top().second] = true;
                pq.pop();
            }
        } else{
            int tmp = x;
            for(int i = LOG - 1; i >= 0; i--){
                if(mark[up[tmp][i]]) tmp = up[tmp][i];
            }

            mark[tmp] = false;
            pq.emplace(t[tmp], tmp);
            cout << depth[x] - depth[tmp] << '\n';
        }
    }

    return 0;
}

Subtask #1
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 5468 KB Output isn't correct
2 Incorrect 71 ms 13684 KB Output isn't correct
3 Incorrect 56 ms 13708 KB Output isn't correct
4 Incorrect 2 ms 5468 KB Output isn't correct
5 Incorrect 1 ms 5468 KB Output isn't correct
6 Incorrect 2 ms 5468 KB Output isn't correct
7 Incorrect 3 ms 5720 KB Output isn't correct
8 Incorrect 2 ms 5468 KB Output isn't correct
9 Incorrect 7 ms 7772 KB Output isn't correct
10 Incorrect 13 ms 8280 KB Output isn't correct
11 Incorrect 62 ms 13524 KB Output isn't correct
12 Incorrect 53 ms 13860 KB Output isn't correct
13 Incorrect 61 ms 13528 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 10332 KB Output is correct
2 Incorrect 147 ms 18696 KB Output isn't correct
3 Incorrect 51 ms 14548 KB Output isn't correct
4 Incorrect 45 ms 10124 KB Output isn't correct
5 Incorrect 44 ms 10028 KB Output isn't correct
6 Incorrect 39 ms 10060 KB Output isn't correct
7 Incorrect 40 ms 9328 KB Output isn't correct
8 Correct 35 ms 10192 KB Output is correct
9 Incorrect 121 ms 19296 KB Output isn't correct
10 Incorrect 107 ms 18740 KB Output isn't correct
11 Incorrect 91 ms 18900 KB Output isn't correct
12 Incorrect 89 ms 16756 KB Output isn't correct
13 Correct 70 ms 22728 KB Output is correct
14 Incorrect 62 ms 14644 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 37 ms 13664 KB Output isn't correct
2 Incorrect 88 ms 17516 KB Output isn't correct
3 Correct 75 ms 21712 KB Output is correct
4 Incorrect 52 ms 17872 KB Output isn't correct
5 Incorrect 57 ms 17676 KB Output isn't correct
6 Incorrect 75 ms 17552 KB Output isn't correct
7 Incorrect 55 ms 16076 KB Output isn't correct
8 Correct 74 ms 21856 KB Output is correct
9 Incorrect 84 ms 19744 KB Output isn't correct
10 Incorrect 128 ms 19324 KB Output isn't correct
11 Incorrect 105 ms 19492 KB Output isn't correct
12 Incorrect 87 ms 17904 KB Output isn't correct
13 Correct 96 ms 24776 KB Output is correct
14 Incorrect 62 ms 15048 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 100 ms 19776 KB Output isn't correct
2 Incorrect 91 ms 17448 KB Output isn't correct
3 Correct 92 ms 24692 KB Output is correct
4 Incorrect 89 ms 19804 KB Output isn't correct
5 Incorrect 107 ms 19408 KB Output isn't correct
6 Incorrect 88 ms 19412 KB Output isn't correct
7 Incorrect 101 ms 17488 KB Output isn't correct
8 Correct 69 ms 24456 KB Output is correct
9 Incorrect 47 ms 14796 KB Output isn't correct