oj.uz

Submission #596154

# Submission time Handle Problem Language Result Execution time Memory
596154 2022-07-14T12:32:07 Z KoD Game (APIO22_game) C++17
2 / 100
 2 ms 464 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);
}

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 2 ms 368 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 2 ms 368 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 0 ms 208 KB Output is correct
14 Correct 1 ms 428 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 208 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Incorrect 1 ms 336 KB Wrong Answer[1]
19 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 2 ms 368 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 0 ms 208 KB Output is correct
14 Correct 1 ms 428 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 208 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Incorrect 1 ms 336 KB Wrong Answer[1]
19 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 2 ms 368 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 0 ms 208 KB Output is correct
14 Correct 1 ms 428 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 208 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Incorrect 1 ms 336 KB Wrong Answer[1]
19 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 2 ms 368 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 0 ms 208 KB Output is correct
14 Correct 1 ms 428 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 208 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Incorrect 1 ms 336 KB Wrong Answer[1]
19 Halted 0 ms 0 KB -