oj.uz

Submission #195626

# Submission time Handle Problem Language Result Execution time Memory
195626 2020-01-16T16:18:46 Z karma Ball Machine (BOI13_ballmachine) C++14
100 / 100
 322 ms 32108 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;

typedef pair<int, int> pii;
int p[N][logN + 1], del[N], d[N], deg[N];
int Min[N], order[N], cur = 0;
int root, n, q, x, k, low, high, mid;
vector<int> a[N];
set<pii> leaf;

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

void Order(int u) {
    vector<pii> child;
    for(int v: a[u]) child.pb(Min[v], v);
    sort(child.begin(), child.end());
    for(pii p: child) Order(p.se);
    order[u] = ++cur;
    if(deg[u] == 0) leaf.insert(mp(order[u], u));
}

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); Order(root);
    while(q --) {
        cin >> x >> k;
        if(x == 1) {
            while(k --) {
                x = (*leaf.begin()).se; leaf.erase(leaf.begin());
                if(--deg[p[x][0]] == 0) leaf.insert(mp(order[p[x][0]], p[x][0]));
                del[x] = 1;
            }
            cout << x << '\n';
        } else {
            x = k;
            for(int i = logN; i >= 0; --i) {
                if(del[p[x][i]]) x = p[x][i];
            }
            del[x] = 0, leaf.insert(mp(order[x], x));
            if(++deg[p[x][0]] == 1) leaf.erase(mp(order[p[x][0]], p[x][0]));
            cout << d[k] - d[x] << '\n';
        }
    }
}

Compilation message

ballmachine.cpp: In function 'int32_t main()':
ballmachine.cpp:50: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:51: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
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2780 KB Output is correct
2 Correct 205 ms 13264 KB Output is correct
3 Correct 95 ms 13120 KB Output is correct
4 Correct 4 ms 2748 KB Output is correct
5 Correct 5 ms 2708 KB Output is correct
6 Correct 5 ms 2812 KB Output is correct
7 Correct 6 ms 2908 KB Output is correct
8 Correct 6 ms 2884 KB Output is correct
9 Correct 14 ms 3424 KB Output is correct
10 Correct 40 ms 5312 KB Output is correct
11 Correct 222 ms 13344 KB Output is correct
12 Correct 130 ms 13108 KB Output is correct
13 Correct 166 ms 13288 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 8516 KB Output is correct
2 Correct 282 ms 23828 KB Output is correct
3 Correct 122 ms 17900 KB Output is correct
4 Correct 113 ms 9640 KB Output is correct
5 Correct 124 ms 9528 KB Output is correct
6 Correct 132 ms 9476 KB Output is correct
7 Correct 120 ms 8204 KB Output is correct
8 Correct 50 ms 8412 KB Output is correct
9 Correct 240 ms 23984 KB Output is correct
10 Correct 269 ms 23744 KB Output is correct
11 Correct 213 ms 23792 KB Output is correct
12 Correct 258 ms 20692 KB Output is correct
13 Correct 155 ms 28036 KB Output is correct
14 Correct 121 ms 17944 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 13508 KB Output is correct
2 Correct 297 ms 21252 KB Output is correct
3 Correct 190 ms 25920 KB Output is correct
4 Correct 184 ms 19764 KB Output is correct
5 Correct 186 ms 19448 KB Output is correct
6 Correct 201 ms 19680 KB Output is correct
7 Correct 190 ms 17460 KB Output is correct
8 Correct 187 ms 25852 KB Output is correct
9 Correct 291 ms 25016 KB Output is correct
10 Correct 302 ms 24056 KB Output is correct
11 Correct 302 ms 24088 KB Output is correct
12 Correct 289 ms 21336 KB Output is correct
13 Correct 296 ms 32108 KB Output is correct
14 Correct 251 ms 18824 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 24356 KB Output is correct
2 Correct 304 ms 21268 KB Output is correct
3 Correct 168 ms 31352 KB Output is correct
4 Correct 302 ms 24428 KB Output is correct
5 Correct 296 ms 24084 KB Output is correct
6 Correct 225 ms 23976 KB Output is correct
7 Correct 287 ms 21468 KB Output is correct
8 Correct 171 ms 31352 KB Output is correct
9 Correct 130 ms 18148 KB Output is correct