Submission #908628

#	Time	Username	Problem	Language	Result	Execution time	Memory
908628		green_gold_dog	Game (APIO22_game)	C++17	2 / 100	1 ms	344 KiB

game

//#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include "game.h"
typedef int ll;

using namespace std;

struct NIGGA {
        vector<vector<ll>> g, rg, gk, rgk;
        vector<ll> d, r, w;
        set<ll> up;
        ll n, k, tk;
        NIGGA(ll xn, ll xk) {
                k = xk;
                n = xn;
                n -= k;
                g.resize(n);
                rg.resize(n);
                gk.resize(n);
                rgk.resize(n);
                tk = k;
                k += 2;
                ll now = 1;
                while (now < k) {
                        d.push_back(now);
                        now *= 2;
                }
                r.resize(n, d.size() - 1);
                w.resize(n, 0);
        }
        bool num(ll& v) {
                if (v < tk) {
                        return true;
                } else {
                        v -= tk;
                        return false;
                }
        }
        void check(ll v, ll i) {
                if (r[i] > r[v] && (w[i] + 1) * d[r[i]] <= w[v] * d[r[v]]) {
                        dfs(i, r[v]);
                }
                if (r[i] == r[v] && w[i] * d[r[i]] < w[v] * d[r[v]]) {
                        dfs(i, r[v] - 1);
                }
        }
        void dfs(ll v, ll nr) {
                while (r[v] > nr) {
                        r[v]--;
                        w[v] *= 2;
                        w[v] += 2;
                }
                up.insert(v);
                if (nr < 0) {
                        return;
                }
                for (auto i : g[v]) {
                        check(v, i);
                }
        }
        void checkr(ll v, ll i) {
                if (r[i] > r[v] && w[i] * d[r[i]] >= w[v] * d[r[v]]) {
                        dfsr(i, r[v]);
                }
                if (r[i] == r[v] && w[i] * d[r[i]] > w[v] * d[r[v]]) {
                        dfsr(i, r[v] - 1);
                }
        }
        void dfsr(ll v, ll nr) {
                while (r[v] > nr) {
                        r[v]--;
                        w[v] *= 2;
                }
                up.insert(v);
                if (nr < 0) {
                        return;
                }
                for (auto i : rg[v]) {
                        checkr(v, i);
                }
        }
        bool add(ll a, ll b) {
                bool b1 = num(a);
                bool b2 = num(b);
                if (!b1 && !b2) {
                        check(a, b);
                        checkr(b, a);
                        g[a].push_back(b);
                        rg[b].push_back(a);
                        return res();
                }
                if (b1 && b2) {
                        if (a >= b) {
                                return true;
                        }
                        return false;
                }
                if (b1) {
                        if ((a + 1) / d[r[b]] > w[b]) {
                                dfs(b, r[b] - 1);
                        }
                        gk[b].push_back(a);
                        return res();
                }
                if (b2) {
                        if ((b + 1) / d[r[a]] <= w[a]) {
                                dfsr(a, r[a] - 1);
                        }
                        rgk[a].push_back(b);
                        return res();
                }
                return false;
        }
        bool res() {
                while (!up.empty()) {
                        ll x = *up.begin();
                        up.erase(up.begin());
                        if (r[x] < 0) {
                                return true;
                        }
                        for (auto i : gk[x]) {
                                if (r[x] < 0) {
                                        break;
                                }
                                if ((i + 1) / d[r[x]] > w[x]) {
                                        dfs(x, r[x] - 1);
                                }
                        }
                        for (auto i : rgk[x]) {
                                if (r[x] < 0) {
                                        break;
                                }
                                if ((i + 1) / d[r[x]] <= w[x]) {
                                        dfsr(x, r[x] - 1);
                                }
                        }
                }
                return false;
        }
};

NIGGA nigger(2, 1);

void init(ll n, ll k) {
        nigger = NIGGA(n, k);
}

int add_teleporter(ll u, ll v) {
        if (nigger.add(u, v)) {
                return 1;
        }
        return 0;
}

#ifdef LOCAL
int main() {
        ll n, m, k;
        cin >> n >> m >> k;
        init(n, k);
        for (ll i = 0; i < m; i++) {
                ll a, b;
                cin >> a >> b;
                cout << add_teleporter(a, b) << '\n';
        }
}
#endif

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