Submission #88246

#	Time	Username	Problem	Language	Result	Execution time	Memory
88246		popovicirobert	Ball Machine (BOI13_ballmachine)	C++14	13.46 / 100	1092 ms	19224 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];

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

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};
}

struct Nod {
    int nod;
    bool operator <(const Nod &other) const {
        pair <int, int> cur = get_lca(nod, other.nod);
        return mn[cur.first] < mn[cur.second];
    }
};

set < Nod > mst;
int deg[MAXN + 1];
bool mark[MAXN + 1];
int weight[MAXN + 1];

inline void add(int nod) {
    int par = anc[nod][0];
    set < Nod > :: iterator it = mst.find({par});
    if(par > 0 && deg[par] == g[par].size()) {
        mst.erase(it);
    }
    mark[nod] = 0;
    mst.insert({nod});
    deg[par]--;
}

inline void del(int nod) {
    mark[nod] = 1;
    set < Nod > :: iterator it = mst.find({nod});
    mst.erase(it);
    int par = anc[nod][0];
    deg[par]++;
    if(par > 0 && deg[par] == g[par].size()) {
        mst.insert({par});
    }
}

int get(int nod) {
    int x = MAXN + 1, id = -1;
    for(auto it : g[nod]) {
        if(x > mn[it] && weight[it] > 0) {
            x = mn[it];
            id = it;
        }
    }
    if(id == -1)
        return nod;
    return get(id);
}

void refresh(int nod) {
    weight[nod] = 1 - mark[nod];
    for(auto it : g[nod]) {
        refresh(it);
        weight[nod] += weight[it];
    }
}

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];
        }
    }
    lvl[root] = 1;
    dfs(root);
    for(i = 1; i <= n; i++) {
        if(g[i].size() == 0) {
            mst.insert({i});
        }
    }
    while(q > 0) {
        refresh(root);
        q--;
        int type, x;
        cin >> type >> x;
        if(type == 1) {
            int nod;
            while(x > 0) {
                refresh(root);
                nod = get(root);
                //cerr << nod << " " << mst.begin() -> nod << "\n";
                if(nod != mst.begin() -> nod) {
                    return -1;
                }
                del(nod);
                //cerr << "\n\n";
                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";
            add(nod);
        }
    }
    //cin.close();
    //cout.close();
    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'void add(int)':
ballmachine.cpp:61:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(par > 0 && deg[par] == g[par].size()) {
                   ~~~~~~~~~^~~~~~~~~~~~~~~~
ballmachine.cpp: In function 'void del(int)':
ballmachine.cpp:75:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(par > 0 && deg[par] == g[par].size()) {
                   ~~~~~~~~~^~~~~~~~~~~~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:148:28: warning: 'nod' may be used uninitialized in this function [-Wmaybe-uninitialized]
             cout << nod << "\n";
                            ^~~~
ballmachine.cpp:138:24: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 refresh(root);
                 ~~~~~~~^~~~~~

• Subtask 1: 13.461538461538462 / 25
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40
• Subtask 4: 0 / 5