Submission #597109

#	Time	Username	Problem	Language	Result	Execution time	Memory
597109		KoD	Game (APIO22_game)	C++17	60 / 100	1682 ms	262144 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using std::pair;
using std::tuple;
using std::queue;
// using std::set;
template <class T> using set = std::unordered_set<T>;
using std::vector;

bool contains(set<int>& set, const int x) {
    return set.find(x) != set.end();
}

struct Interval {
    int mid, par, lch, rch;
    set<int> from, to;
    explicit Interval(const int m) : mid(m), par(-1), lch(-1), rch(-1), from(), to() {}
};

int N, K;
vector<vector<int>> graph, revgraph;
vector<Interval> segtree;

int build(int l, int r) {
    const int u = (int)segtree.size();
    const int m = (l + r) / 2;
    segtree.emplace_back(m);
    if (l < m) {
        segtree[u].lch = build(l, m);
        segtree[segtree[u].lch].par = u;
    }
    if (m + 1 < r) {
        segtree[u].rch = build(m + 1, r);
        segtree[segtree[u].rch].par = u;
    }
    for (int i = l; i < m; ++i)
        segtree[u].from.insert(i);
    for (int i = m + 1; i < r; ++i)
        segtree[u].to.insert(i);
    return u;
}

bool check(int x, int u) {
    const int p = segtree[x].par;
    if (p == -1) {
        return true;
    } else {
        if (segtree[p].lch == x) {
            return contains(segtree[p].from, u);
        } else {
            return contains(segtree[p].to, u);
        }
    }
}

void init(int n, int k) {
    N = n;
    K = k;
    graph.resize(n);
    revgraph.resize(n);
    build(0, k);
}

vector<tuple<int, int, int>> stack;

bool insert_recursive(int x, int u) {
    auto& data = segtree[x];
    if (!check(x, u))
        return false;
    if (data.mid == u)
        return true;
    if (data.to.insert(u).second) {
        if (contains(data.from, u))
            return true;
        for (const int v : graph[u])
            stack.emplace_back(x, u, v);
    }
    return false;
}

bool insert_recursive_rev(int x, int u) {
    auto& data = segtree[x];
    if (!check(x, u))
        return false;
    if (data.mid == u)
        return true;
    if (data.from.insert(u).second) {
        if (contains(data.to, u))
            return true;
        for (const int v : revgraph[u])
            stack.emplace_back(x, v, u);
    }
    return false;
}

bool add_recursive(int x, int u, int v) {
    auto& data = segtree[x];
    if ((contains(data.from, v) or v == data.mid)) {
        if (insert_recursive_rev(x, u))
            return true;
        if (data.lch != -1)
            stack.emplace_back(data.lch, u, v);
    }
    if ((contains(data.to, u) or u == data.mid)) {
        if (insert_recursive(x, v))
            return true;
        if (data.rch != -1)
            stack.emplace_back(data.rch, u, v);
    }
    return false;
}

int add_teleporter(int u, int v) {
    graph[u].push_back(v);
    revgraph[v].push_back(u);
    stack.emplace_back(0, u, v);
    while (!stack.empty()) {
        const auto [x, u, v] = stack.back();
        stack.pop_back();
        if (add_recursive(x, u, v))
            return true;
    }
    return false;
}

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