oj.uz

Submission #525624

# Submission time Handle Problem Language Result Execution time Memory
525624 2022-02-12T07:36:11 Z crap_the_coder Ball Machine (BOI13_ballmachine) C++17
16.1111 / 100
 371 ms 24680 KB 
// https://gist.github.com/Juanito98/c53793b4e084f989e975b9c7879c0d43

#include <bits/stdc++.h>
#define optimizar ios_base::sync_with_stdio(0); cin.tie(0)
#define lld long long int
using namespace std;
const int MAXN = 100002;
const int LOG_N = 20;

int n, Q, root;
vector < int > adj[MAXN];
int depth[MAXN], padre[MAXN][LOG_N];
set < int > libre;
int id[MAXN], realNum[MAXN];

int cont;
void dfs(int v) {
    depth[v] = depth[padre[v][0]] + 1;
    for(int i = 1; i < LOG_N; i++)
        padre[v][i] = padre[padre[v][i - 1]][i - 1];

    for(int i = 0; i < adj[v].size(); i++) dfs(adj[v][i]);
    id[v] = ++cont;
    realNum[cont] = v;
}

int erase(int v) {
    int u = v;
    for(int i = LOG_N - 1; i >= 0; i--) {
        if(!libre.count(id[padre[u][i]]) && padre[u][i])
            u = padre[u][i];
    }
    libre.insert(id[u]);
    return depth[v] - depth[u];
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> Q;
    for(int i = 1; i <= n; i++) {
        libre.insert(i);
        int p;
        cin >> p;
        if(!p) root = i;
        else {
            padre[i][0] = p;
            adj[p].push_back(i);
        }
    }

    for(int i = 1; i <= n; i++) sort(adj[i].begin(), adj[i].end());
    dfs(root);

    int last = 0;
    for(int i = 1; i <= Q; i++) {
        int a, b;
        cin >> a >> b;
        if(a == 1) {
            for(int j = 1; j <= b; j++) {
                set < int > :: iterator it = libre.begin();
                last = realNum[*it];
                libre.erase(*it);
            }
            cout << last << "\n";
        } else {
            cout << erase(b) << "\n";
        }
    }
    return 0;
}

Compilation message

ballmachine.cpp: In function 'void dfs(int)':
ballmachine.cpp:22:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i = 0; i < adj[v].size(); i++) dfs(adj[v][i]);
      |                    ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Incorrect 156 ms 12936 KB Output isn't correct
3 Incorrect 82 ms 13004 KB Output isn't correct
4 Incorrect 2 ms 2692 KB Output isn't correct
5 Incorrect 2 ms 2636 KB Output isn't correct
6 Incorrect 2 ms 2764 KB Output isn't correct
7 Incorrect 2 ms 2764 KB Output isn't correct
8 Incorrect 2 ms 2764 KB Output isn't correct
9 Incorrect 10 ms 3276 KB Output isn't correct
10 Incorrect 26 ms 5212 KB Output isn't correct
11 Incorrect 163 ms 13068 KB Output isn't correct
12 Incorrect 80 ms 12972 KB Output isn't correct
13 Incorrect 125 ms 12804 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 6868 KB Output is correct
2 Incorrect 308 ms 21444 KB Output isn't correct
3 Incorrect 91 ms 18024 KB Output isn't correct
4 Incorrect 119 ms 8460 KB Output isn't correct
5 Incorrect 153 ms 8592 KB Output isn't correct
6 Incorrect 150 ms 8560 KB Output isn't correct
7 Incorrect 155 ms 7672 KB Output isn't correct
8 Correct 46 ms 6756 KB Output is correct
9 Incorrect 231 ms 21444 KB Output isn't correct
10 Incorrect 314 ms 21508 KB Output isn't correct
11 Incorrect 254 ms 21128 KB Output isn't correct
12 Incorrect 301 ms 19524 KB Output isn't correct
13 Correct 135 ms 21944 KB Output is correct
14 Incorrect 92 ms 18028 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 106 ms 11948 KB Output isn't correct
2 Incorrect 342 ms 19784 KB Output isn't correct
3 Correct 248 ms 20168 KB Output is correct
4 Incorrect 166 ms 17744 KB Output isn't correct
5 Incorrect 225 ms 17200 KB Output isn't correct
6 Incorrect 213 ms 17164 KB Output isn't correct
7 Incorrect 206 ms 16324 KB Output isn't correct
8 Correct 236 ms 20180 KB Output is correct
9 Incorrect 256 ms 21316 KB Output isn't correct
10 Incorrect 335 ms 21124 KB Output isn't correct
11 Incorrect 330 ms 20968 KB Output isn't correct
12 Incorrect 332 ms 19724 KB Output isn't correct
13 Correct 371 ms 24644 KB Output is correct
14 Incorrect 145 ms 17856 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 282 ms 21904 KB Output isn't correct
2 Incorrect 335 ms 19780 KB Output isn't correct
3 Correct 159 ms 24508 KB Output is correct
4 Incorrect 287 ms 21876 KB Output isn't correct
5 Incorrect 363 ms 20956 KB Output isn't correct
6 Incorrect 278 ms 20900 KB Output isn't correct
7 Incorrect 333 ms 19780 KB Output isn't correct
8 Correct 168 ms 24680 KB Output is correct
9 Incorrect 89 ms 17956 KB Output isn't correct