oj.uz

Submission #102324

# Submission time Handle Problem Language Result Execution time Memory
102324 2019-03-24T10:28:40 Z MoNsTeR_CuBe Ball Machine (BOI13_ballmachine) C++17
100 / 100
 503 ms 43396 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

vector< vector<int> > Graph;

vector< vector< pair<int, int> > > minChildren;

const int INF = 1e15;

int dfs(int x, int last){
    int mini = INF;
    minChildren[x].clear();
    for(int a : Graph[x]){
        if(a == last) continue;
        int b = dfs(a,x);
        mini = min(mini, b);
        minChildren[x].push_back(make_pair(b, a));
    }
    if(!Graph[x].size()){
        return x;
    }
    //cout << "NODE " << x << ' ' << minChildren[x].size() << endl;
    sort(minChildren[x].begin(), minChildren[x].end());
    return min(x, mini);
}

vector< bool > isFull;

vector<int> priority;

priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > pq;

int curr = 0;

vector< int> depth;

void add(int node, int d){
    depth[node] = d;
    for(auto a : minChildren[node]){
        add(a.second,d+1);
    }
    priority[node] = curr++;
    pq.push(make_pair(priority[node], node));
}

vector< int > up;

int tot ;

vector< vector< int > > parents;

void calc(int n){
    for(int i = 1; i<=n; i++){
        parents[0][i] = up[i];
        if(parents[0][i] == 0) parents[0][i] = -1;
    }
    for(int i = 1; i < 20; i++){
        for(int j = 1; j <= n; j++){
            if(parents[i-1][j] != -1)
                parents[i][j] = parents[i-1][parents[i-1][j]];
            else parents[i][j] = -1;
        }
    }
}

int ans(int x){
    int s = depth[x];
    int b = x;
    for(int i = 19; i >= 0; i--){
        if(parents[i][x] != -1 && isFull[parents[i][x]]){
            x = parents[i][x];
        }
    }
    int ar = depth[x];
    int ans = s-ar;
    if(ans != 0){
        isFull[x] = false;
        pq.push({priority[x],x});
        isFull[b] = true;
    }else{
        pq.push({priority[b], b});
    }
    return ans;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    Graph.resize(n+1);
    int root;
    up.resize(n+1);
    priority.resize(n+1);
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        Graph[a].push_back(i+1);
        up[i+1] = a;
        if(a == 0) root = i+1;
    }

    minChildren.resize(n+1);
    depth.resize(n+1);
    dfs(root,-1);
    add(root,0);

    isFull.resize(n+1);

    parents.resize(20, vector<int>(n+1));

    calc(n);

    while(q--){
        int a;
        cin >> a;
        int b;
        cin >> b;
        if(a == 1){
            int last = 0;
            for(int i = 0; i < b; i++){
                last = pq.top().second;
                isFull[last] = true;
                pq.pop();
            }
            cout << last << endl;
        }else{
            isFull[b] = false;
            cout << ans(b) << endl;
        }
    }
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:108:8: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
     add(root,0);
     ~~~^~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 293 ms 19692 KB Output is correct
3 Correct 249 ms 19820 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 4 ms 640 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 26 ms 1536 KB Output is correct
10 Correct 51 ms 5376 KB Output is correct
11 Correct 293 ms 19536 KB Output is correct
12 Correct 235 ms 19820 KB Output is correct
13 Correct 313 ms 19564 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 8304 KB Output is correct
2 Correct 425 ms 35860 KB Output is correct
3 Correct 248 ms 29424 KB Output is correct
4 Correct 213 ms 11264 KB Output is correct
5 Correct 202 ms 11120 KB Output is correct
6 Correct 217 ms 11128 KB Output is correct
7 Correct 236 ms 9584 KB Output is correct
8 Correct 149 ms 8432 KB Output is correct
9 Correct 380 ms 36416 KB Output is correct
10 Correct 358 ms 35816 KB Output is correct
11 Correct 416 ms 35948 KB Output is correct
12 Correct 410 ms 32364 KB Output is correct
13 Correct 308 ms 38088 KB Output is correct
14 Correct 247 ms 29288 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 18620 KB Output is correct
2 Correct 445 ms 33220 KB Output is correct
3 Correct 296 ms 34540 KB Output is correct
4 Correct 313 ms 29552 KB Output is correct
5 Correct 285 ms 28904 KB Output is correct
6 Correct 287 ms 28776 KB Output is correct
7 Correct 309 ms 26728 KB Output is correct
8 Correct 308 ms 34568 KB Output is correct
9 Correct 395 ms 36596 KB Output is correct
10 Correct 433 ms 36128 KB Output is correct
11 Correct 419 ms 36184 KB Output is correct
12 Correct 478 ms 33308 KB Output is correct
13 Correct 493 ms 43396 KB Output is correct
14 Correct 312 ms 29432 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 36736 KB Output is correct
2 Correct 430 ms 33272 KB Output is correct
3 Correct 328 ms 43144 KB Output is correct
4 Correct 503 ms 36792 KB Output is correct
5 Correct 406 ms 36076 KB Output is correct
6 Correct 336 ms 35948 KB Output is correct
7 Correct 389 ms 33260 KB Output is correct
8 Correct 276 ms 43044 KB Output is correct
9 Correct 265 ms 29432 KB Output is correct