oj.uz

Submission #160486

# Submission time Handle Problem Language Result Execution time Memory
160486 2019-10-27T18:27:02 Z tushar_2658 Ball Machine (BOI13_ballmachine) C++14
77.4359 / 100
 1000 ms 32632 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);
    }
    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; (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:69: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:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
         ~~~~~^~~~~~~~~~
ballmachine.cpp:86: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 2680 KB Output isn't correct
2 Execution timed out 1076 ms 14968 KB Time limit exceeded
3 Correct 117 ms 15224 KB Output is correct
4 Execution timed out 1073 ms 2680 KB Time limit exceeded
5 Incorrect 4 ms 2684 KB Output isn't correct
6 Correct 5 ms 2936 KB Output is correct
7 Execution timed out 1086 ms 2808 KB Time limit exceeded
8 Incorrect 5 ms 2804 KB Output isn't correct
9 Execution timed out 1077 ms 3448 KB Time limit exceeded
10 Execution timed out 1085 ms 5880 KB Time limit exceeded
11 Incorrect 167 ms 14968 KB Output isn't correct
12 Correct 115 ms 15224 KB Output is correct
13 Incorrect 145 ms 14968 KB Output isn't correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 8568 KB Output is correct
2 Correct 258 ms 27340 KB Output is correct
3 Correct 159 ms 21436 KB Output is correct
4 Correct 103 ms 10320 KB Output is correct
5 Correct 100 ms 10360 KB Output is correct
6 Correct 97 ms 10360 KB Output is correct
7 Correct 94 ms 9000 KB Output is correct
8 Correct 57 ms 8696 KB Output is correct
9 Correct 222 ms 26964 KB Output is correct
10 Correct 245 ms 27256 KB Output is correct
11 Correct 218 ms 27384 KB Output is correct
12 Correct 243 ms 23972 KB Output is correct
13 Correct 174 ms 28920 KB Output is correct
14 Correct 158 ms 21352 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 15096 KB Output is correct
2 Correct 290 ms 24532 KB Output is correct
3 Correct 205 ms 26608 KB Output is correct
4 Correct 184 ms 22400 KB Output is correct
5 Correct 196 ms 22520 KB Output is correct
6 Correct 184 ms 22420 KB Output is correct
7 Correct 187 ms 20216 KB Output is correct
8 Correct 207 ms 26700 KB Output is correct
9 Correct 276 ms 27112 KB Output is correct
10 Correct 290 ms 27512 KB Output is correct
11 Correct 368 ms 27532 KB Output is correct
12 Correct 289 ms 24568 KB Output is correct
13 Correct 297 ms 32632 KB Output is correct
14 Correct 222 ms 21608 KB Output is correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 260 ms 27128 KB Output isn't correct
2 Incorrect 277 ms 24576 KB Output isn't correct
3 Correct 208 ms 32376 KB Output is correct
4 Incorrect 275 ms 27128 KB Output isn't correct
5 Incorrect 260 ms 27480 KB Output isn't correct
6 Incorrect 242 ms 27276 KB Output isn't correct
7 Incorrect 282 ms 24568 KB Output isn't correct
8 Correct 195 ms 32264 KB Output is correct
9 Correct 149 ms 21348 KB Output is correct