oj.uz

Submission #524422

# Submission time Handle Problem Language Result Execution time Memory
524422 2022-02-09T07:59:49 Z IMystic Ball Machine (BOI13_ballmachine) C++17
100 / 100
 270 ms 28244 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 100010, INF = 1000000000;
vector<int> adj[N];
vector<int> mn, dist;
vector<pair<int, bool>> order;

int lg = 1;
void dfs(int n, int par){
    sort(adj[n].begin(), adj[n].end(), [](int a, int b){return mn[a] < mn[b];});
    if(par != -1)dist[n] = dist[par] + 1;
    lg = max(lg, dist[n]);
    for(int c : adj[n]){
        if(c != par){
            dfs(c, n);
        }
    }
    order.emplace_back(n, false);
}

void init(int n, int par){
    mn[n] = n;
    for(int c : adj[n]){
        if(c != par){
            init(c, n);
            mn[n] = min(mn[n], mn[c]);
        }
    }
}

int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, root;
    cin >> n >> m;
    vector<int> p(n);
    for(int i=0; i<n; i++){
        cin >> p[i];
        --p[i];
        if(p[i] != -1){
            adj[i].push_back(p[i]);
            adj[p[i]].push_back(i);
        }else root = i;
    } 
    vector<int> id(n);
    
    dist.resize(n, INF);
    mn.resize(n, INF);
    dist[root] = 0;
    init(root, -1);
    dfs(root, -1);

    for(int i=0; i<n; i++)id[order[i].first] = i;

    set<int> tofill;
    for(int i=0; i<n; i++)tofill.insert(i);
    
    lg = 32 - __builtin_clz(lg + 1);
    vector<int> B[lg];
    {   
        B[0].resize(n);
        B[0][root] = root;
        for(int i=0; i<n; i++)if(p[i] != -1)B[0][i] = p[i];
        for(int c=1; c<lg; c++){
            B[c].resize(n);
            for(int i=0; i<n; i++){
                B[c][i] = B[c-1][B[c-1][i]];
            }
        }
    }

    

    p[root] = root;
    for(int i=0; i<m; i++){
        int t, x;
        cin >> t >> x;
        if(t & 1){
            vector<int> tem;
            auto it = tofill.begin();
            while(x--){
                assert(it != tofill.end());
                order[*it].second = true;
                tem.push_back(*it);
                ++it;
            }
            cout << order[tem.back()].first + 1 << '\n';
            for(int &c : tem)tofill.erase(c);
        }else {
            --x;
            int y = x;
           // while(y != p[y] && order[id[p[y]]].second)y = p[y];
            for(int i = lg - 1; i>=0; i--){
                if(order[id[B[i][y]]].second)y = B[i][y];
            }
           // cout << y << '\n';
            order[id[y]].second = false;
            tofill.insert(id[y]);
            cout << dist[x] - dist[y] << '\n';
        }
    }

    return 0;
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:77:13: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |     p[root] = root;

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 112 ms 11240 KB Output is correct
3 Correct 62 ms 10904 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2764 KB Output is correct
7 Correct 2 ms 2764 KB Output is correct
8 Correct 2 ms 2792 KB Output is correct
9 Correct 6 ms 3160 KB Output is correct
10 Correct 20 ms 4764 KB Output is correct
11 Correct 107 ms 11140 KB Output is correct
12 Correct 61 ms 10944 KB Output is correct
13 Correct 118 ms 10876 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 7232 KB Output is correct
2 Correct 248 ms 23620 KB Output is correct
3 Correct 80 ms 14648 KB Output is correct
4 Correct 87 ms 8924 KB Output is correct
5 Correct 101 ms 8792 KB Output is correct
6 Correct 90 ms 8688 KB Output is correct
7 Correct 84 ms 7668 KB Output is correct
8 Correct 34 ms 7240 KB Output is correct
9 Correct 212 ms 23720 KB Output is correct
10 Correct 270 ms 23736 KB Output is correct
11 Correct 187 ms 23248 KB Output is correct
12 Correct 216 ms 20844 KB Output is correct
13 Correct 114 ms 24752 KB Output is correct
14 Correct 105 ms 14684 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 13104 KB Output is correct
2 Correct 263 ms 21492 KB Output is correct
3 Correct 157 ms 23280 KB Output is correct
4 Correct 129 ms 19768 KB Output is correct
5 Correct 148 ms 19776 KB Output is correct
6 Correct 146 ms 19692 KB Output is correct
7 Correct 146 ms 17728 KB Output is correct
8 Correct 130 ms 23228 KB Output is correct
9 Correct 254 ms 23864 KB Output is correct
10 Correct 252 ms 23872 KB Output is correct
11 Correct 264 ms 23868 KB Output is correct
12 Correct 261 ms 21500 KB Output is correct
13 Correct 221 ms 28244 KB Output is correct
14 Correct 143 ms 15588 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 24236 KB Output is correct
2 Correct 255 ms 21440 KB Output is correct
3 Correct 116 ms 27668 KB Output is correct
4 Correct 218 ms 24044 KB Output is correct
5 Correct 237 ms 23872 KB Output is correct
6 Correct 179 ms 23288 KB Output is correct
7 Correct 247 ms 21360 KB Output is correct
8 Correct 112 ms 27700 KB Output is correct
9 Correct 84 ms 14748 KB Output is correct