Submission #699272

#	Time	Username	Problem	Language	Result	Execution time	Memory
699272		KoD	Game (APIO22_game)	C++17	100 / 100	1528 ms	68032 KiB

game

#include "game.h"
#include <algorithm>
#include <utility>
#include <vector>

namespace kod {

using namespace std;

int n, k;
vector<int> l, r;
vector<vector<int>> in, out;

int get_level(const int u) { return l[u] >= r[u] ? 0 : 32 - __builtin_clz(l[u] ^ r[u]); }

bool check_vertex(const int u);
bool check_edge(const int u, const int v);

bool check_vertex(const int x) {
    for (const int y : out[x]) {
        if (check_edge(x, y)) {
            return true;
        }
    }
    for (const int y : in[x]) {
        if (check_edge(y, x)) {
            return true;
        }
    }
    return false;
}

bool check_edge(const int u, const int v) {
    const int u0 = get_level(u);
    const int v0 = get_level(v);
    r[u] = min(r[u], v <= k ? v : r[v]);
    l[v] = max(l[v], u <= k ? u : l[u]);
    const int u1 = get_level(u);
    const int v1 = get_level(v);
    if (u1 == 0 or v1 == 0) return true;
    if (u1 < u0 and check_vertex(u)) return true;
    if (v1 < v0 and check_vertex(v)) return true;
    return false;
}

int add_edge(const int u, const int v) {
    in[v].push_back(u);
    out[u].push_back(v);
    return check_edge(u, v);
}

void init(const int n_, const int k_) {
    n = n_;
    k = k_;
    l.resize(n + 1, 0);
    r.resize(n + 1, k + 1);
    in.resize(n + 1);
    out.resize(n + 1);
    for (int i = 1; i <= k - 1; ++i) {
        in[i + 1].push_back(i);
        out[i].push_back(i + 1);
        r[i] = i + 1;
        l[i + 1] = i;
    }
}

}  // namespace kod

void init(int n, int k) { kod::init(n, k); }

int add_teleporter(int u, int v) { return kod::add_edge(u + 1, v + 1); }

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