oj.uz

Submission #410710

# Submission time Handle Problem Language Result Execution time Memory
410710 2021-05-23T12:22:39 Z LptN21 Ball Machine (BOI13_ballmachine) C++14
0 / 100
 524 ms 26236 KB 
#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];
                cout << "add to " << last << "\n";
                libre.erase(*it);
            }
            cout << last << "\n";
        } else {
            cout << erase(b) << "\n";
        }
    }
    return 0;
}

Compilation message

ballmachine.cpp: In function 'void dfs(int)':
ballmachine.cpp:21:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     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 226 ms 14380 KB Output isn't correct
3 Incorrect 105 ms 13628 KB Output isn't correct
4 Incorrect 2 ms 2636 KB Output isn't correct
5 Incorrect 2 ms 2636 KB Output isn't correct
6 Incorrect 3 ms 2844 KB Output isn't correct
7 Incorrect 3 ms 2764 KB Output isn't correct
8 Incorrect 4 ms 2764 KB Output isn't correct
9 Incorrect 13 ms 3404 KB Output isn't correct
10 Incorrect 39 ms 5700 KB Output isn't correct
11 Incorrect 262 ms 14404 KB Output isn't correct
12 Incorrect 104 ms 13648 KB Output isn't correct
13 Incorrect 176 ms 14148 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 7588 KB Output isn't correct
2 Incorrect 419 ms 23304 KB Output isn't correct
3 Incorrect 128 ms 18588 KB Output isn't correct
4 Incorrect 200 ms 9664 KB Output isn't correct
5 Incorrect 243 ms 9284 KB Output isn't correct
6 Incorrect 192 ms 9336 KB Output isn't correct
7 Incorrect 204 ms 8652 KB Output isn't correct
8 Incorrect 75 ms 7620 KB Output isn't correct
9 Incorrect 325 ms 23076 KB Output isn't correct
10 Incorrect 418 ms 23456 KB Output isn't correct
11 Incorrect 362 ms 22336 KB Output isn't correct
12 Incorrect 444 ms 20896 KB Output isn't correct
13 Incorrect 233 ms 22980 KB Output isn't correct
14 Incorrect 136 ms 18536 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 163 ms 12740 KB Output isn't correct
2 Incorrect 484 ms 21392 KB Output isn't correct
3 Incorrect 337 ms 20932 KB Output isn't correct
4 Incorrect 234 ms 18400 KB Output isn't correct
5 Incorrect 302 ms 17964 KB Output isn't correct
6 Incorrect 332 ms 18196 KB Output isn't correct
7 Incorrect 296 ms 17232 KB Output isn't correct
8 Incorrect 323 ms 21104 KB Output isn't correct
9 Incorrect 361 ms 22704 KB Output isn't correct
10 Incorrect 474 ms 22332 KB Output isn't correct
11 Incorrect 446 ms 22344 KB Output isn't correct
12 Incorrect 507 ms 21532 KB Output isn't correct
13 Incorrect 511 ms 26236 KB Output isn't correct
14 Incorrect 209 ms 19184 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 373 ms 23256 KB Output isn't correct
2 Incorrect 449 ms 21676 KB Output isn't correct
3 Incorrect 235 ms 25540 KB Output isn't correct
4 Incorrect 390 ms 23352 KB Output isn't correct
5 Incorrect 524 ms 22348 KB Output isn't correct
6 Incorrect 392 ms 22272 KB Output isn't correct
7 Incorrect 473 ms 21604 KB Output isn't correct
8 Incorrect 237 ms 25760 KB Output isn't correct
9 Incorrect 152 ms 18356 KB Output isn't correct