Submission #88241

#	Time	Username	Problem	Language	Result	Execution time	Memory
88241		popovicirobert	Ball Machine (BOI13_ballmachine)	C++14	32.44 / 100	1088 ms	20420 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];

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 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});
        }
    }
    int black = 0;
    while(q > 0) {
        q--;
        int type, x;
        cin >> type >> x;
        if(type == 1) {
            int nod;
            while(x > 0 && black < n) {
                nod = mst.begin() -> nod;
                //cerr << nod << "\n";
                del(nod);
                /*cerr << mst.size() << "\n";
                for(auto it : mst) {
                    cerr << it.nod << " ";
                }
                cerr << "\n";*/
                x--;
                black++;
            }
            //cerr << "\n";
            cout << nod << "\n";
        }
        else {
            int nod = x;
            for(int bit = LOG; bit >= 0; bit--) {
                if(mark[anc[nod][bit]]) {
                    nod = anc[nod][bit];
                }
            }
            //cerr << nod << "\n";
            cout << lvl[x] - lvl[nod] << "\n";
            add(nod);
            /*for(i = 1; i <= n; i++) {
                cerr << mark[i] << " ";
            }
            cerr << "\n";
            for(auto it : mst) {
                cerr << it.nod << " ";
            }
            cerr << "\n\n";*/
        }
    }
    //cin.close();
    //cout.close();
    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'void add(int)':
ballmachine.cpp:60: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:74: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:128:28: warning: 'nod' may be used uninitialized in this function [-Wmaybe-uninitialized]
             cout << nod << "\n";
                            ^~~~
ballmachine.cpp:102:8: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
     dfs(root);
     ~~~^~~~~~

• Subtask 1: 5.769230769230769 / 25
• Subtask 2: 10.714285714285714 / 30
• Subtask 3: 14.285714285714286 / 40
• Subtask 4: 1.6666666666666667 / 5