oj.uz

Submission #160487

# Submission time Handle Problem Language Result Execution time Memory
160487 2019-10-27T18:32:01 Z tushar_2658 Ball Machine (BOI13_ballmachine) C++14
77.4359 / 100
 1000 ms 33912 KB 
#include "bits/stdc++.h"
using namespace std;

const int maxn = 100005;
int par[maxn], root;
vector<int> edges[maxn]; 
int depth[maxn], dp[maxn], n, m;

void dfs(int x, int p){
    depth[x] = depth[p] + 1;
    dp[x] = x;
    vector<pair<int, int>> all;
    for(auto i : edges[x]){
        if(i == p)continue; 
        dfs(i, x);
        all.push_back({dp[i], i});
        dp[x] = min(dp[x], dp[i]);
    }
    sort(all.begin(), all.end()); 
    edges[x].clear();
    for(auto i : all){
        edges[x].push_back(i.second);
    }
    edges[x].push_back(p);
}   

set<pair<int, int>> st;
int ed[maxn], cnt = 0;

void dfs1(int x, int p){
    for(auto i : edges[x]){
        if(i == p)continue;
        dfs1(i, x);
    }
    ed[x] = ++cnt;
    st.insert({cnt, x});
}

int sparse[maxn][22];

void build(){
    for(int i = 1; i <= n; i++){
        sparse[i][0] = par[i];
    }
    for(int j = 1; j < 20; j++){
        for(int i = 1; i <= n; i++){
            if(sparse[i][j - 1] != 0){
                sparse[i][j] = sparse[sparse[i][j - 1]][j - 1];
            }
        }
    }
}

bool status[maxn];

int first_empty(int x){
    for(int i = 20; i >= 0; i--){
        if(sparse[x][i] != 0 && status[sparse[x][i]] != 0){
            x = sparse[x][i];
        }
    }
    return x;
}

int main(int argc, char const *argv[])
{
//    freopen("in.txt", "r", stdin);
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++){
        int x; 
        scanf("%d", &x);
        if(x != 0){
            edges[i].push_back(x); 
            edges[x].push_back(i);
            par[i] = x;
        }else {
            root = i;
        }
    }
    dfs(root, -1);
    dfs1(root, -1);
    build();
    while(m--){
        int t, x;
        scanf("%d %d", &t, &x); 
        if(t == 1){
            pair<int, int> last;
            for(int i = 0; i < x; i++){
                last = *st.begin();
                st.erase(st.begin());
                status[last.second] = 1;
            }
            printf("%d\n", last.second);
        }else {
            int ff = first_empty(x);
            status[ff] = 0;
            st.insert({ed[x], x});
            printf("%d\n", depth[x] - depth[ff]);
        }
    }

    return 0;
}

Compilation message

ballmachine.cpp: In function 'int main(int, const char**)':
ballmachine.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
ballmachine.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
         ~~~~~^~~~~~~~~~
ballmachine.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &t, &x); 
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.76923076923 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2808 KB Output isn't correct
2 Execution timed out 1079 ms 14840 KB Time limit exceeded
3 Correct 113 ms 15072 KB Output is correct
4 Execution timed out 1083 ms 2684 KB Time limit exceeded
5 Incorrect 5 ms 2680 KB Output isn't correct
6 Correct 5 ms 2808 KB Output is correct
7 Execution timed out 1071 ms 2812 KB Time limit exceeded
8 Incorrect 5 ms 2808 KB Output isn't correct
9 Execution timed out 1090 ms 3448 KB Time limit exceeded
10 Execution timed out 1088 ms 5752 KB Time limit exceeded
11 Incorrect 154 ms 14840 KB Output isn't correct
12 Correct 141 ms 15060 KB Output is correct
13 Incorrect 149 ms 15060 KB Output isn't correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 8696 KB Output is correct
2 Correct 267 ms 27292 KB Output is correct
3 Correct 145 ms 21220 KB Output is correct
4 Correct 105 ms 10420 KB Output is correct
5 Correct 102 ms 10208 KB Output is correct
6 Correct 91 ms 10232 KB Output is correct
7 Correct 93 ms 8864 KB Output is correct
8 Correct 65 ms 8632 KB Output is correct
9 Correct 223 ms 27384 KB Output is correct
10 Correct 246 ms 27512 KB Output is correct
11 Correct 223 ms 27340 KB Output is correct
12 Correct 339 ms 23796 KB Output is correct
13 Correct 170 ms 30180 KB Output is correct
14 Correct 136 ms 21176 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 15192 KB Output is correct
2 Correct 274 ms 24400 KB Output is correct
3 Correct 187 ms 27760 KB Output is correct
4 Correct 171 ms 22520 KB Output is correct
5 Correct 264 ms 22560 KB Output is correct
6 Correct 180 ms 22552 KB Output is correct
7 Correct 178 ms 20036 KB Output is correct
8 Correct 204 ms 27700 KB Output is correct
9 Correct 271 ms 27512 KB Output is correct
10 Correct 281 ms 27612 KB Output is correct
11 Correct 285 ms 27632 KB Output is correct
12 Correct 278 ms 24440 KB Output is correct
13 Correct 283 ms 33912 KB Output is correct
14 Correct 219 ms 21392 KB Output is correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 257 ms 27608 KB Output isn't correct
2 Incorrect 262 ms 24440 KB Output isn't correct
3 Correct 197 ms 33772 KB Output is correct
4 Incorrect 251 ms 27640 KB Output isn't correct
5 Incorrect 268 ms 27512 KB Output isn't correct
6 Incorrect 219 ms 27476 KB Output isn't correct
7 Incorrect 268 ms 24400 KB Output isn't correct
8 Correct 183 ms 33656 KB Output is correct
9 Correct 133 ms 21220 KB Output is correct