oj.uz

Submission #160485

# Submission time Handle Problem Language Result Execution time Memory
160485 2019-10-27T18:24:07 Z tushar_2658 Ball Machine (BOI13_ballmachine) C++14
77.4359 / 100
 1000 ms 33784 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] = (p != -1) ? depth[p] + 1 : 0;
    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[i.second].push_back(x);
    }
}   

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; (1 << j) <= n; 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 2812 KB Output isn't correct
2 Execution timed out 1074 ms 15864 KB Time limit exceeded
3 Correct 106 ms 15992 KB Output is correct
4 Execution timed out 1080 ms 2680 KB Time limit exceeded
5 Incorrect 4 ms 2808 KB Output isn't correct
6 Correct 5 ms 2936 KB Output is correct
7 Execution timed out 1085 ms 2936 KB Time limit exceeded
8 Incorrect 5 ms 2808 KB Output isn't correct
9 Execution timed out 1076 ms 3448 KB Time limit exceeded
10 Execution timed out 1079 ms 5880 KB Time limit exceeded
11 Incorrect 161 ms 15864 KB Output isn't correct
12 Correct 104 ms 15864 KB Output is correct
13 Incorrect 139 ms 15864 KB Output isn't correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 8824 KB Output is correct
2 Correct 268 ms 27956 KB Output is correct
3 Correct 152 ms 21988 KB Output is correct
4 Correct 100 ms 10792 KB Output is correct
5 Correct 99 ms 10616 KB Output is correct
6 Correct 93 ms 10744 KB Output is correct
7 Correct 100 ms 9464 KB Output is correct
8 Correct 54 ms 8824 KB Output is correct
9 Correct 238 ms 27896 KB Output is correct
10 Correct 243 ms 27884 KB Output is correct
11 Correct 218 ms 27904 KB Output is correct
12 Correct 233 ms 24568 KB Output is correct
13 Correct 167 ms 29816 KB Output is correct
14 Correct 160 ms 22008 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 15364 KB Output is correct
2 Correct 277 ms 25192 KB Output is correct
3 Correct 190 ms 27128 KB Output is correct
4 Correct 176 ms 22776 KB Output is correct
5 Correct 171 ms 22776 KB Output is correct
6 Correct 178 ms 22732 KB Output is correct
7 Correct 172 ms 20556 KB Output is correct
8 Correct 304 ms 27348 KB Output is correct
9 Correct 298 ms 28024 KB Output is correct
10 Correct 289 ms 28068 KB Output is correct
11 Correct 264 ms 28028 KB Output is correct
12 Correct 274 ms 25336 KB Output is correct
13 Correct 298 ms 33784 KB Output is correct
14 Correct 210 ms 22504 KB Output is correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 234 ms 28280 KB Output isn't correct
2 Incorrect 266 ms 25208 KB Output isn't correct
3 Correct 183 ms 33144 KB Output is correct
4 Incorrect 235 ms 28164 KB Output isn't correct
5 Incorrect 239 ms 28024 KB Output isn't correct
6 Incorrect 232 ms 27896 KB Output isn't correct
7 Incorrect 266 ms 25464 KB Output isn't correct
8 Correct 186 ms 33272 KB Output is correct
9 Correct 135 ms 22120 KB Output is correct