Submission #981745

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
981745	2024-05-13T14:01:06 Z	crafticat	Game (APIO22_game)	C++17	2 / 100	1 ms	344 KB

game

#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 : gr[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 : g[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 && u < K) {
        pos = false;
        return 1;
    }

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

Subtask #1

2.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	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct

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	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Incorrect	1 ms	344 KB	Wrong Answer[1]
12	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	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Incorrect	1 ms	344 KB	Wrong Answer[1]
12	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	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Incorrect	1 ms	344 KB	Wrong Answer[1]
12	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	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Incorrect	1 ms	344 KB	Wrong Answer[1]
12	Halted	0 ms	0 KB	-