oj.uz

Submission #368220

# Submission time Handle Problem Language Result Execution time Memory
368220 2021-02-19T19:24:35 Z ritul_kr_singh Ball Machine (BOI13_ballmachine) C++14
100 / 100
 639 ms 40972 KB 
//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << " " <<
#define nl << "\n"
 
int n, q, subMin[100000], root;
vector<vector<int>> g;
vector<int> seq, ind_in_seq;
int up[100000][18], depth[100000];
 
void dfs0(int u, int d){
    depth[u] = d;
    if(u==root) for(int i=0; i<18; ++i) up[u][i] = u;
    else for(int i=1; i<18; ++i)  up[u][i] = up[up[u][i-1]][i-1];
    subMin[u] = u;
    for(int v : g[u]){
        dfs0(v, d+1);
        subMin[u] = min(subMin[u], subMin[v]);
    }
}
 
void dfs1(int u){
    vector<pair<int, int>> vs;
    for(int v : g[u]){
        vs.emplace_back(subMin[v], v);
    }
    sort(vs.begin(), vs.end());
    for(auto v : vs) {
        dfs1(v.second);
    }
    ind_in_seq[u] = seq.size();
    seq.push_back(u);
}
 
signed main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> q;
    for(int i=0; i<n; ++i) cin >> up[i][0], --up[i][0];
    g.resize(n);
    for(int i=0; i<n; ++i){
        if(up[i][0]==-1) root = i;
        else g[up[i][0]].push_back(i);
    }
    dfs0(root, 0);
    ind_in_seq.resize(n);
    dfs1(root);
  
    set<int> toAdd;
    for(int i=0; i<n; ++i) toAdd.emplace(i);
    int type, k;
    while(q--){
        cin >> type >> k;
        int ans = 0;
        if(type==1){
            for(int i=0; i<k; ++i){
                ans = seq[*toAdd.begin()];
                toAdd.erase(toAdd.begin());
            }
            cout << ans+1 nl;
        }else{
            --k;
            int start = k;
            for(int i=17; i>=0; --i){
                while(up[k][i] != k and toAdd.find(ind_in_seq[up[k][i]])==toAdd.end()) k = up[k][i];
            }
            toAdd.insert(ind_in_seq[k]);
            cout << depth[start] - depth[k] nl;
        }
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 440 KB Output is correct
2 Correct 408 ms 18660 KB Output is correct
3 Correct 192 ms 18660 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 12 ms 1516 KB Output is correct
10 Correct 44 ms 4844 KB Output is correct
11 Correct 415 ms 18708 KB Output is correct
12 Correct 185 ms 18704 KB Output is correct
13 Correct 360 ms 18660 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 8332 KB Output is correct
2 Correct 630 ms 34104 KB Output is correct
3 Correct 252 ms 27272 KB Output is correct
4 Correct 223 ms 11004 KB Output is correct
5 Correct 294 ms 10944 KB Output is correct
6 Correct 283 ms 10864 KB Output is correct
7 Correct 271 ms 9320 KB Output is correct
8 Correct 89 ms 8304 KB Output is correct
9 Correct 441 ms 34180 KB Output is correct
10 Correct 571 ms 34040 KB Output is correct
11 Correct 502 ms 33852 KB Output is correct
12 Correct 543 ms 30436 KB Output is correct
13 Correct 263 ms 35980 KB Output is correct
14 Correct 253 ms 27336 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 17356 KB Output is correct
2 Correct 604 ms 31308 KB Output is correct
3 Correct 417 ms 32804 KB Output is correct
4 Correct 335 ms 27792 KB Output is correct
5 Correct 417 ms 27452 KB Output is correct
6 Correct 378 ms 27516 KB Output is correct
7 Correct 400 ms 24844 KB Output is correct
8 Correct 381 ms 32748 KB Output is correct
9 Correct 479 ms 34280 KB Output is correct
10 Correct 601 ms 34024 KB Output is correct
11 Correct 580 ms 34024 KB Output is correct
12 Correct 565 ms 31256 KB Output is correct
13 Correct 620 ms 40972 KB Output is correct
14 Correct 293 ms 27736 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 508 ms 34528 KB Output is correct
2 Correct 616 ms 31288 KB Output is correct
3 Correct 264 ms 40588 KB Output is correct
4 Correct 483 ms 34388 KB Output is correct
5 Correct 639 ms 34016 KB Output is correct
6 Correct 460 ms 34236 KB Output is correct
7 Correct 605 ms 31356 KB Output is correct
8 Correct 226 ms 40544 KB Output is correct
9 Correct 242 ms 27480 KB Output is correct