oj.uz

Submission #908630

# Submission time Handle Problem Language Result Execution time Memory
908630 2024-01-16T15:38:22 Z green_gold_dog Game (APIO22_game) C++17
2 / 100
 1 ms 420 KB 
//#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, -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, -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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 420 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 420 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Incorrect 1 ms 344 KB Wrong Answer[1]
17 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 420 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Incorrect 1 ms 344 KB Wrong Answer[1]
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 420 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Incorrect 1 ms 344 KB Wrong Answer[1]
17 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 420 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Incorrect 1 ms 344 KB Wrong Answer[1]
17 Halted 0 ms 0 KB -