oj.uz

답안 #666931

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
666931 2022-11-30T00:29:01 Z Hacv16 Ball Machine (BOI13_ballmachine) C++17
100 / 100
 229 ms 127792 KB 
#include<bits/stdc++.h>
using namespace std;
     
typedef long long ll;
     
const int MAX = 1e6 + 10;
const int LOG = 22;
const int INF = 0x3f3f3f3f;
     
int n, q, filled[MAX], root, t, order[MAX], dp[MAX][LOG], d[MAX], mn[MAX];
vector<int> adj[MAX];
set<pair<int, int>> s;
       
bool cmp(int u, int v){ return mn[u] < mn[v]; }

void dfs(int u, int p, int dist){
    d[u] = dist, mn[u] = u;
     
    for(auto v : adj[u]){
        if(v == p) continue;
        dfs(v, u, dist + 1);
        mn[u] = min(mn[u], mn[v]);
    }

    sort(adj[u].begin(), adj[u].end(), cmp);
}

void dfs2(int u, int p){
    for(auto v : adj[u]){
        if(v == p) continue;
        dfs2(v, u);
    }
     
    order[u] = ++t;
    s.insert({order[u], u});
}
     
int query(ll u){
    int old = d[u];
     
    for(int i = LOG - 1; i >= 0; i--){
        int j = dp[u][i];
        if(j == -1) continue;
        if(filled[j]) u = j;
    }

    s.insert({order[u], u});
    filled[u] = false;
     
    return old - d[u];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
     
    cin >> n >> q;
     
    memset(dp, -1, sizeof(dp));
     
    for(int i = 1; i <= n; i++){
        int x; cin >> x;
     
        if(x != 0){
            adj[x].push_back(i);
            adj[i].push_back(x);
            dp[i][0] = x;
     
        }else{ root = i; }
    }
     
    dfs(root, -1, 0);
    dfs2(root, -1);
     
    for(int j = 1; j < LOG; j++){
        for(int i = 1; i <= n; i++){
            if(dp[i][j - 1] == -1) continue;
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
        }
    }
     
    while(q--){
        int op, k; cin >> op >> k;
     
        if(op == 1){
            int last = -1;
     
            while(k-- && s.size()){
                int cur = (*(s.begin())).second;
                filled[cur] = true;
                last = cur;
     
                s.erase(s.begin());
            }
     
            cout << last << '\n';
     
        }else{
            cout << query(k) << '\n';
        }
    }
     
    return 0;
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 109896 KB Output is correct
2 Correct 143 ms 116252 KB Output is correct
3 Correct 99 ms 116204 KB Output is correct
4 Correct 43 ms 109824 KB Output is correct
5 Correct 45 ms 109868 KB Output is correct
6 Correct 46 ms 110012 KB Output is correct
7 Correct 46 ms 109996 KB Output is correct
8 Correct 53 ms 109916 KB Output is correct
9 Correct 54 ms 110268 KB Output is correct
10 Correct 61 ms 111416 KB Output is correct
11 Correct 158 ms 116264 KB Output is correct
12 Correct 99 ms 116152 KB Output is correct
13 Correct 126 ms 116236 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 113268 KB Output is correct
2 Correct 214 ms 123432 KB Output is correct
3 Correct 127 ms 119240 KB Output is correct
4 Correct 102 ms 113996 KB Output is correct
5 Correct 104 ms 114036 KB Output is correct
6 Correct 97 ms 114052 KB Output is correct
7 Correct 99 ms 113148 KB Output is correct
8 Correct 74 ms 113232 KB Output is correct
9 Correct 171 ms 123388 KB Output is correct
10 Correct 201 ms 123388 KB Output is correct
11 Correct 186 ms 123512 KB Output is correct
12 Correct 178 ms 121184 KB Output is correct
13 Correct 134 ms 125128 KB Output is correct
14 Correct 124 ms 119240 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 116832 KB Output is correct
2 Correct 214 ms 121596 KB Output is correct
3 Correct 172 ms 124104 KB Output is correct
4 Correct 146 ms 120764 KB Output is correct
5 Correct 148 ms 120780 KB Output is correct
6 Correct 146 ms 120744 KB Output is correct
7 Correct 151 ms 119168 KB Output is correct
8 Correct 175 ms 124048 KB Output is correct
9 Correct 207 ms 123596 KB Output is correct
10 Correct 229 ms 123556 KB Output is correct
11 Correct 229 ms 123596 KB Output is correct
12 Correct 216 ms 121672 KB Output is correct
13 Correct 214 ms 127792 KB Output is correct
14 Correct 195 ms 119716 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 218 ms 123688 KB Output is correct
2 Correct 227 ms 121712 KB Output is correct
3 Correct 149 ms 127388 KB Output is correct
4 Correct 218 ms 123728 KB Output is correct
5 Correct 213 ms 123596 KB Output is correct
6 Correct 187 ms 123680 KB Output is correct
7 Correct 227 ms 121616 KB Output is correct
8 Correct 184 ms 127472 KB Output is correct
9 Correct 136 ms 119368 KB Output is correct