oj.uz

Submission #673832

# Submission time Handle Problem Language Result Execution time Memory
673832 2022-12-22T08:50:53 Z Cookie Ball Machine (BOI13_ballmachine) C++14
100 / 100
 163 ms 30740 KB 
#include<bits/stdc++.h>

#include<fstream>

using namespace std;
ifstream fin("INTERNET.INP");
ofstream fout("INTERNET.OUT");
#define ll long long
#define vt vector
#define pb push_back
#define fi first
#define se second
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define int long long
const int mxn = 1e5, sq = 300, mxv = 1e4;
const int inf = 1e9;
int n, q, root;
vt<int>adj[mxn + 1];
int pos[mxn + 1], t = 1, dep[mxn + 1], mn[mxn + 1];
int up[mxn  +1][17];
bool used[mxn + 1];
void dfs2(int s, int pre){
    mn[s] = s;
    for(auto i: adj[s]){
        if(i != pre){
            dfs2(i, s);
            mn[s] = min(mn[s], mn[i]);
        }
    }
}
bool cmp2(int a, int b){
    return(mn[a] < mn[b]);
}
void dfs(int s, int pre){
    sort(adj[s].begin(), adj[s].end(), cmp2);
    for(auto i: adj[s]){
        if(i != pre){
            dep[i] = dep[s] + 1;
            dfs(i, s); up[i][0] = s;
        }
    }
    pos[s] = t++;
}
struct cmp{
    bool operator ()(int a, int b){
        return(pos[a] > pos[b]);
    }
};
priority_queue<int, vt<int>, cmp>pq;
int lift(int x){
    int ans = x;
    for(int i = 16; i >= 0; i--){
        if(up[ans][i] && used[up[ans][i]]){
            ans = up[ans][i];
        }
    }
    return(ans);
}
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        int v; cin >> v;
        if(!v)root = i;
        else adj[v].pb(i);
    }
    dfs2(root, -1);
    dfs(root, -1);
    used[0] = true; //avoid mistake
    for(int i = 1; i <= n; i++){
        pq.push(i); used[i] = false;
    }
    for(int i = 1; i < 17; i++){
        for(int j = 1; j <= n; j++){
            up[j][i] = up[up[j][i - 1]][i - 1];
        }
    }
    for(int i = 0; i < q; i++){
        int idq; cin >> idq;
        if(idq == 1){
            int k; cin >> k;
            int cr;
            for(int j = 0; j < k; j++){
                cr = pq.top(); pq.pop(); used[cr] = true; 
            }
            cout << cr << "\n";
        }else{
            int x; cin >> x;
            int highest = lift(x); pq.push(highest); used[highest] = false;
            cout << dep[x] - dep[highest] << "\n";
        }
    }
    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 86 ms 16016 KB Output is correct
3 Correct 57 ms 16020 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2812 KB Output is correct
7 Correct 2 ms 2816 KB Output is correct
8 Correct 2 ms 2816 KB Output is correct
9 Correct 5 ms 3540 KB Output is correct
10 Correct 16 ms 6028 KB Output is correct
11 Correct 86 ms 15996 KB Output is correct
12 Correct 53 ms 16036 KB Output is correct
13 Correct 85 ms 15948 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 8256 KB Output is correct
2 Correct 134 ms 26032 KB Output is correct
3 Correct 81 ms 21952 KB Output is correct
4 Correct 53 ms 10388 KB Output is correct
5 Correct 53 ms 10224 KB Output is correct
6 Correct 55 ms 10256 KB Output is correct
7 Correct 53 ms 9244 KB Output is correct
8 Correct 29 ms 8272 KB Output is correct
9 Correct 119 ms 26448 KB Output is correct
10 Correct 138 ms 26044 KB Output is correct
11 Correct 116 ms 26144 KB Output is correct
12 Correct 121 ms 23996 KB Output is correct
13 Correct 88 ms 27172 KB Output is correct
14 Correct 76 ms 21952 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 14736 KB Output is correct
2 Correct 141 ms 24644 KB Output is correct
3 Correct 106 ms 24788 KB Output is correct
4 Correct 87 ms 21696 KB Output is correct
5 Correct 94 ms 21460 KB Output is correct
6 Correct 85 ms 21284 KB Output is correct
7 Correct 86 ms 20056 KB Output is correct
8 Correct 104 ms 24732 KB Output is correct
9 Correct 138 ms 26756 KB Output is correct
10 Correct 146 ms 26256 KB Output is correct
11 Correct 145 ms 26180 KB Output is correct
12 Correct 136 ms 24612 KB Output is correct
13 Correct 163 ms 30740 KB Output is correct
14 Correct 100 ms 22536 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 26688 KB Output is correct
2 Correct 139 ms 24792 KB Output is correct
3 Correct 103 ms 30188 KB Output is correct
4 Correct 155 ms 26660 KB Output is correct
5 Correct 141 ms 26212 KB Output is correct
6 Correct 109 ms 26216 KB Output is correct
7 Correct 135 ms 24640 KB Output is correct
8 Correct 103 ms 30212 KB Output is correct
9 Correct 77 ms 22080 KB Output is correct