oj.uz

Submission #195590

# Submission time Handle Problem Language Result Execution time Memory
195590 2020-01-16T14:47:14 Z karma Ball Machine (BOI13_ballmachine) C++14
20.9524 / 100
 927 ms 21944 KB 
#include <bits/stdc++.h>
#define pb          emplace_back
#define ll          long long
#define fi          first
#define se          second
#define mp          make_pair
//#define int         int64_t

using namespace std;

const int N = (int)1e5 + 2;
const int logN = 20;

int p[N][logN + 1], del[N], d[N], deg[N];
int root, n, q, x, k, low, high, mid;
vector<int> a[N];
set<int> leaf;

void DFS(int u) {
    deg[u] = a[u].size();
    for(int i = 1; i <= logN; ++i) p[u][i] = p[p[u][i - 1]][i - 1];
    if(!deg[u]) leaf.insert(u);
    for(int v: a[u]) d[v] = d[u] + 1, DFS(v);
}

int Node(int x, int step) {
    for(int i = logN; i >= 0; --i)
        if(step >= (1 << i)) x = p[x][i], step -= (1 << i);
    return x;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define Task        "test"
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n >> q;
    for(int i = 1; i <= n; ++i) {
        cin >> p[i][0]; a[p[i][0]].pb(i);
        if(!p[i][0]) root = i;
    }
    DFS(root);
    while(q --) {
        cin >> x >> k;
        if(x == 1) {
            while(k --) {
                x = *leaf.begin(); leaf.erase(x);
                if(--deg[p[x][0]] == 0) leaf.insert(p[x][0]);
                del[x] = 1;
            }
            cout << x << '\n';
        } else {
            low = 0, high = d[k];
            while(low <= high) {
                mid = (low + high) >> 1;
                if(del[Node(k, mid)]) low = mid + 1;
                else high = mid - 1;
            }
            x = Node(k, high), del[x] = 0, leaf.insert(x);
            if(++deg[p[x][0]] == 1) leaf.erase(p[x][0]);
            cout << d[k] - d[x] << '\n';
        }
    }
}

Compilation message

ballmachine.cpp: In function 'int32_t main()':
ballmachine.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2808 KB Output isn't correct
2 Incorrect 204 ms 12792 KB Output isn't correct
3 Incorrect 100 ms 12408 KB Output isn't correct
4 Incorrect 8 ms 2680 KB Output isn't correct
5 Incorrect 5 ms 2680 KB Output isn't correct
6 Incorrect 5 ms 2808 KB Output isn't correct
7 Incorrect 6 ms 2936 KB Output isn't correct
8 Incorrect 6 ms 2808 KB Output isn't correct
9 Incorrect 12 ms 3320 KB Output isn't correct
10 Incorrect 33 ms 5112 KB Output isn't correct
11 Incorrect 202 ms 12836 KB Output isn't correct
12 Incorrect 91 ms 12676 KB Output isn't correct
13 Incorrect 154 ms 12764 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 6692 KB Output is correct
2 Incorrect 797 ms 20608 KB Output isn't correct
3 Correct 118 ms 17240 KB Output is correct
4 Incorrect 139 ms 8696 KB Output isn't correct
5 Incorrect 195 ms 8924 KB Output isn't correct
6 Incorrect 206 ms 8468 KB Output isn't correct
7 Incorrect 227 ms 8056 KB Output isn't correct
8 Correct 74 ms 6652 KB Output is correct
9 Incorrect 390 ms 20956 KB Output isn't correct
10 Incorrect 565 ms 20472 KB Output isn't correct
11 Incorrect 376 ms 19704 KB Output isn't correct
12 Incorrect 425 ms 18548 KB Output isn't correct
13 Correct 139 ms 19064 KB Output is correct
14 Correct 116 ms 17160 KB Output is correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 205 ms 11336 KB Output isn't correct
2 Incorrect 927 ms 18932 KB Output isn't correct
3 Correct 490 ms 17948 KB Output is correct
4 Incorrect 254 ms 16248 KB Output isn't correct
5 Incorrect 395 ms 16324 KB Output isn't correct
6 Incorrect 547 ms 16248 KB Output isn't correct
7 Incorrect 557 ms 15356 KB Output isn't correct
8 Correct 448 ms 17828 KB Output is correct
9 Incorrect 407 ms 19812 KB Output isn't correct
10 Incorrect 565 ms 19988 KB Output isn't correct
11 Incorrect 601 ms 19868 KB Output isn't correct
12 Incorrect 867 ms 18952 KB Output isn't correct
13 Correct 818 ms 21944 KB Output is correct
14 Incorrect 355 ms 18044 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 742 ms 19960 KB Output isn't correct
2 Incorrect 605 ms 18680 KB Output isn't correct
3 Correct 164 ms 21184 KB Output is correct
4 Incorrect 580 ms 20012 KB Output isn't correct
5 Incorrect 542 ms 19900 KB Output isn't correct
6 Incorrect 344 ms 19944 KB Output isn't correct
7 Incorrect 522 ms 18876 KB Output isn't correct
8 Correct 151 ms 21236 KB Output is correct
9 Correct 112 ms 17316 KB Output is correct