oj.uz

Submission #981699

# Submission time Handle Problem Language Result Execution time Memory
981699 2024-05-13T13:14:27 Z crafticat Game (APIO22_game) C++17
0 / 100
 1 ms 344 KB 
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> g;
vector<vector<int>> gr;
constexpr int inf = 1e9;
int K = 0;
vector<int> toMin, fromMax;
bool pos = true;

void init(int n, int k) {
    g.resize(n + 1);
    gr.resize(n + 1);
    toMin.resize(n + 1,inf);
    fromMax.resize(n + 1,-1);
    K = k;

    for (int i = 0; i < k; ++i) {
        toMin[i] = i;
        fromMax[i] = i;
    }
    for (int i = 0; i < k - 1; ++i) {
        g[i].push_back(i + 1);
        gr[i + 1].push_back(i);
    }
}

// U -> V
bool push(int x) {
    if (fromMax[x] >= toMin[x] && x >= K)
        return true;
    for (auto par : g[x]) {
        if (toMin[par] > toMin[x]) {
            toMin[par] = toMin[x];
            if (push(par)) return true;
        }
    }
    return false;
}
bool push2(int x) {
    if (fromMax[x] >= toMin[x] && x >= K)
        return true;
    for (auto par : gr[x]) {
        if (fromMax[par] < fromMax[x]) {
            fromMax[par] = fromMax[x];
            if (push2(par)) return true;
        }
    }
    return false;
}

int add_teleporter(int u, int v) {
    if (!pos) return 1;

    if (u == v && v < K) {
        pos = false;
        return 1;
    }

    toMin[u] = min(toMin[v],toMin[u]);
    if (push(u)) pos = false;
    fromMax[v] = max(fromMax[v], fromMax[u]);
    if (push2(v)) pos = false;
    g[u].push_back(v);
    g[v].push_back(u);
    gr[v].push_back(u);
    gr[u].push_back(v);
    return !pos;
}

Subtask #1
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 1 ms 344 KB Wrong Answer[1]
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 1 ms 344 KB Wrong Answer[1]
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 1 ms 344 KB Wrong Answer[1]
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 1 ms 344 KB Wrong Answer[1]
5 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 1 ms 344 KB Wrong Answer[1]
5 Halted 0 ms 0 KB -