Submission #596154

#	Time	Username	Problem	Language	Result	Execution time	Memory
596154		KoD	게임 (APIO22_game)	C++17	2 / 100	2 ms	464 KiB

game

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

using std::pair;
using std::queue;
using std::set;
using std::vector;

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

struct Interval {
    int left, mid, right;
    int lch, rch;
    set<int> from, to;
    explicit Interval(const int l, const int r) : left(l), mid((l + r) / 2), right(r), lch(-1), rch(-1), from(), to() {}
};

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

int build(int l, int r) {
    const int u = (int)segtree.size();
    segtree.emplace_back(l, r);
    const int m = (l + r) / 2;
    if (l < m) segtree[u].lch = build(l, m);
    if (m + 1 < r) segtree[u].rch = build(m + 1, r);
    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;
}

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

bool insert_recursive(int x, int u) {
    auto& data = segtree[x];
    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]) if (insert_recursive(x, v)) return true;
    }
    return false;
}

bool insert_recursive_rev(int x, int u) {
    auto& data = segtree[x];
    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]) if (insert_recursive_rev(x, v)) return true;
    }
    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 and add_recursive(data.lch, u, v)) return true;
    }
    if (contains(data.to, u) or u == data.mid) {
        if (insert_recursive(x, v)) return true;
        if (data.rch != -1 and add_recursive(data.rch, u, v)) return true;
    }
    if (contains(data.from, u) or u == data.mid) {
        if (data.lch != -1 and add_recursive(data.lch, u, v)) return true;
    }
    if (contains(data.to, v) or v == data.mid) {
        if (data.rch != -1 and add_recursive(data.rch, u, v)) return true;
    }
    return false;
}

int add_teleporter(int u, int v) {
    graph[u].push_back(v);
    revgraph[v].push_back(u);
    return add_recursive(0, u, v);
}

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