oj.uz

Submission #88249

# Submission time Handle Problem Language Result Execution time Memory
88249 2018-12-04T19:43:51 Z popovicirobert Ball Machine (BOI13_ballmachine) C++14
100 / 100
 570 ms 25076 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const int MAXN = (int) 1e5;
const int LOG = 17;

vector <int> g[MAXN + 1];
int mn[MAXN + 1], lvl[MAXN + 1];
int l[MAXN + 1], r[MAXN + 1], sz;

void dfs(int nod) {
    l[nod] = ++sz;
    mn[nod] = nod;
    for(auto it : g[nod]) {
        lvl[it] = lvl[nod] + 1;
        dfs(it);
        mn[nod] = min(mn[nod], mn[it]);
    }
    r[nod] = sz;
}

int anc[MAXN + 1][LOG + 1];

inline pair <int, int> get_lca(int x, int y) {
    for(int bit = LOG; bit >= 0; bit--) {
        if(lvl[x] > lvl[y] && lvl[anc[x][bit]] >= lvl[y]) {
            x = anc[x][bit];
        }
        if(lvl[y] > lvl[x] && lvl[anc[y][bit]] >= lvl[x]) {
            y = anc[y][bit];
        }
    }
    for(int bit = LOG; bit >= 0; bit--) {
        if(anc[x][bit] != anc[y][bit]) {
            x = anc[x][bit];
            y = anc[y][bit];
        }
    }
    return {x, y};
}

int pos[MAXN + 1], where[MAXN + 1];

bool cmp(int a, int b) {
    if(l[a] <= l[b] && r[b] <= r[a]) {
        return 0;
    }
    if(l[b] <= l[a] && r[a] <= r[b]) {
        return 1;
    }
    pair <int, int> cur = get_lca(a, b);
    return mn[cur.first] < mn[cur.second];
}

int aib[MAXN + 1];

inline void update(int pos, int n, int val) {
    for(int i = pos; i <= n; i += lsb(i)) {
        aib[i] += val;
    }
}

bool mark[MAXN + 1];

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, q;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> q;
    int root;
    for(i = 1; i <= n; i++) {
        int par;
        cin >> par;
        g[par].push_back(i);
        anc[i][0] = par;
        if(par == 0) {
            root = i;
        }
    }
    for(int bit = 1; bit <= LOG; bit++) {
        for(i = 1; i <= n; i++) {
            anc[i][bit] = anc[anc[i][bit - 1]][bit - 1];
        }
    }
    dfs(root);
    for(i = 1; i <= n; i++) {
        pos[i] = i;
    }
    sort(pos + 1, pos + n + 1, cmp);
    for(i = 1; i <= n; i++) {
        where[pos[i]] = i;
    }
    while(q > 0) {
        q--;
        int type, x;
        cin >> type >> x;
        if(type == 1) {
            int nod;
            while(x > 0) {
                int res = 0, sum = 0;
                for(int step = 1 << LOG; step; step >>= 1) {
                    if(res + step <= n && sum + aib[res + step] == res + step) {
                        res += step;
                        sum += aib[res];
                    }
                }
                res++;
                update(res, n, 1);
                mark[pos[res]] = 1;
                nod = pos[res];
                x--;
            }
            cout << nod << "\n";
        }
        else {
            int nod = x;
            for(int bit = LOG; bit >= 0; bit--) {
                if(mark[anc[nod][bit]]) {
                    nod = anc[nod][bit];
                }
            }
            cout << lvl[x] - lvl[nod] << "\n";
            mark[nod] = 0;
            update(where[nod], n, -1);
        }
    }
    //cin.close();
    //cout.close();
    return 0;
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:121:28: warning: 'nod' may be used uninitialized in this function [-Wmaybe-uninitialized]
             cout << nod << "\n";
                            ^~~~
ballmachine.cpp:93:8: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
     dfs(root);
     ~~~^~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 309 ms 10620 KB Output is correct
3 Correct 252 ms 10620 KB Output is correct
4 Correct 4 ms 10620 KB Output is correct
5 Correct 5 ms 10620 KB Output is correct
6 Correct 6 ms 10620 KB Output is correct
7 Correct 6 ms 10620 KB Output is correct
8 Correct 6 ms 10620 KB Output is correct
9 Correct 16 ms 10620 KB Output is correct
10 Correct 59 ms 10620 KB Output is correct
11 Correct 283 ms 10968 KB Output is correct
12 Correct 264 ms 10968 KB Output is correct
13 Correct 304 ms 10968 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 10968 KB Output is correct
2 Correct 500 ms 18036 KB Output is correct
3 Correct 369 ms 18036 KB Output is correct
4 Correct 125 ms 18036 KB Output is correct
5 Correct 121 ms 18036 KB Output is correct
6 Correct 128 ms 18036 KB Output is correct
7 Correct 144 ms 18036 KB Output is correct
8 Correct 44 ms 18036 KB Output is correct
9 Correct 407 ms 18404 KB Output is correct
10 Correct 532 ms 18696 KB Output is correct
11 Correct 536 ms 18776 KB Output is correct
12 Correct 537 ms 18776 KB Output is correct
13 Correct 120 ms 20648 KB Output is correct
14 Correct 445 ms 20648 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 20648 KB Output is correct
2 Correct 531 ms 20648 KB Output is correct
3 Correct 143 ms 20648 KB Output is correct
4 Correct 292 ms 20648 KB Output is correct
5 Correct 344 ms 20648 KB Output is correct
6 Correct 334 ms 20648 KB Output is correct
7 Correct 385 ms 20648 KB Output is correct
8 Correct 142 ms 20648 KB Output is correct
9 Correct 413 ms 20648 KB Output is correct
10 Correct 490 ms 20648 KB Output is correct
11 Correct 498 ms 20720 KB Output is correct
12 Correct 504 ms 20720 KB Output is correct
13 Correct 237 ms 25056 KB Output is correct
14 Correct 476 ms 25056 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 25056 KB Output is correct
2 Correct 570 ms 25056 KB Output is correct
3 Correct 128 ms 25056 KB Output is correct
4 Correct 466 ms 25056 KB Output is correct
5 Correct 521 ms 25056 KB Output is correct
6 Correct 497 ms 25056 KB Output is correct
7 Correct 473 ms 25056 KB Output is correct
8 Correct 127 ms 25076 KB Output is correct
9 Correct 391 ms 25076 KB Output is correct