Submission #88249

#	Time	Username	Problem	Language	Result	Execution time	Memory
88249		popovicirobert	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	570 ms	25076 KiB

ballmachine

#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 (stderr)

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 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5