Submission #88229

#	Time	Username	Problem	Language	Result	Execution time	Memory
88229		popovicirobert	Ball Machine (BOI13_ballmachine)	C++14	0 / 100	217 ms	17276 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[anc[x][bit]] >= lvl[y]) {
            x = anc[x][bit];
        }
        else if(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);
        /*if(mn[cur.first] == mn[cur.second]) {
            assert(1);
        }*/
        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()) {
        /*if(it == mst.end()) {
            assert(1);
        }*/
        mst.erase(it);
    }
    mark[nod] = 0;
    mst.insert({nod});
    deg[par]--;
}

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

Compilation message (stderr)

ballmachine.cpp: In function 'void add(int)':
ballmachine.cpp:63: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:79:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(par > 0 && deg[par] == g[par].size()) {
                   ~~~~~~~~~^~~~~~~~~~~~~~~~

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