oj.uz

답안 #596102

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
596102 2022-07-14T11:25:16 Z KoD 게임 (APIO22_game) C++17
0 / 100
 0 ms 208 KB 
#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 - 1);
}

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

bool insert_recursive_rev(int x, int u) {
    auto& data = segtree[x];
    if (data.from.insert(u).second) {
        if (contains(data.to, u)) return true;
        for (const int v : revgraph[u]) insert_recursive_rev(x, v);
    }
    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) add_recursive(data.lch, u, v);
    }
    if (contains(data.to, u) or u == data.mid) {
        if (insert_recursive(x, v)) return true;
        if (data.lch != -1) add_recursive(data.lch, u, v);
    }
    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
0.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Incorrect 0 ms 208 KB Wrong Answer[1]
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Incorrect 0 ms 208 KB Wrong Answer[1]
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Incorrect 0 ms 208 KB Wrong Answer[1]
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Incorrect 0 ms 208 KB Wrong Answer[1]
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Incorrect 0 ms 208 KB Wrong Answer[1]
3 Halted 0 ms 0 KB -