Submission #726949

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
726949	2023-04-19T16:29:58 Z	vjudge1	Game (APIO22_game)	C++17	2 / 100	16 ms	23916 KB

game

#include <bits/stdc++.h>
using namespace std;
#include "game.h"

int N, K;
int f[300000];
vector<int> adj[300000], radj[300000];

void init(int n, int k) {
        N = n, K = k;
        for (int i = 0; i < N; i++) f[i] = N;
}

priority_queue<pair<int, int>> pq[300000];

int add_teleporter(int u, int v) {
        adj[u].emplace_back(v);
        radj[v].emplace_back(u);
        pq[v].emplace(f[u], u);
        int F = v < K ? v : f[v];
        queue<int> q;
        q.emplace(v);
        while (q.size()) {
                int v = q.front();
                q.pop();
                while (pq[v].size()) {
                        auto [fu, u] = pq[v].top();
                        if (fu <= F) break;
                        pq[v].pop();
                        if (f[u] != fu) continue;
                        f[u] = F;
                        pq[v].emplace(f[u], u);
                        q.emplace(u);
                }
        }
        for (int i = 0; i < K; i++) {
                if (f[i] <= i) return 1;
        }
        return 0;
}

Subtask #1

2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	23692 KB	Output is correct
2	Correct	12 ms	23660 KB	Output is correct
3	Correct	14 ms	23760 KB	Output is correct
4	Correct	13 ms	23760 KB	Output is correct
5	Correct	13 ms	23760 KB	Output is correct
6	Correct	14 ms	23916 KB	Output is correct
7	Correct	12 ms	23760 KB	Output is correct

Subtask #2

0.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	23692 KB	Output is correct
2	Correct	12 ms	23660 KB	Output is correct
3	Correct	14 ms	23760 KB	Output is correct
4	Correct	13 ms	23760 KB	Output is correct
5	Correct	13 ms	23760 KB	Output is correct
6	Correct	14 ms	23916 KB	Output is correct
7	Correct	12 ms	23760 KB	Output is correct
8	Correct	12 ms	23760 KB	Output is correct
9	Correct	13 ms	23716 KB	Output is correct
10	Correct	13 ms	23748 KB	Output is correct
11	Incorrect	13 ms	23724 KB	Wrong Answer[1]
12	Halted	0 ms	0 KB	-

Subtask #3

0.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	23692 KB	Output is correct
2	Correct	12 ms	23660 KB	Output is correct
3	Correct	14 ms	23760 KB	Output is correct
4	Correct	13 ms	23760 KB	Output is correct
5	Correct	13 ms	23760 KB	Output is correct
6	Correct	14 ms	23916 KB	Output is correct
7	Correct	12 ms	23760 KB	Output is correct
8	Correct	12 ms	23760 KB	Output is correct
9	Correct	13 ms	23716 KB	Output is correct
10	Correct	13 ms	23748 KB	Output is correct
11	Incorrect	13 ms	23724 KB	Wrong Answer[1]
12	Halted	0 ms	0 KB	-

Subtask #4

0.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	23692 KB	Output is correct
2	Correct	12 ms	23660 KB	Output is correct
3	Correct	14 ms	23760 KB	Output is correct
4	Correct	13 ms	23760 KB	Output is correct
5	Correct	13 ms	23760 KB	Output is correct
6	Correct	14 ms	23916 KB	Output is correct
7	Correct	12 ms	23760 KB	Output is correct
8	Correct	12 ms	23760 KB	Output is correct
9	Correct	13 ms	23716 KB	Output is correct
10	Correct	13 ms	23748 KB	Output is correct
11	Incorrect	13 ms	23724 KB	Wrong Answer[1]
12	Halted	0 ms	0 KB	-

Subtask #5

0.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	23692 KB	Output is correct
2	Correct	12 ms	23660 KB	Output is correct
3	Correct	14 ms	23760 KB	Output is correct
4	Correct	13 ms	23760 KB	Output is correct
5	Correct	13 ms	23760 KB	Output is correct
6	Correct	14 ms	23916 KB	Output is correct
7	Correct	12 ms	23760 KB	Output is correct
8	Correct	12 ms	23760 KB	Output is correct
9	Correct	13 ms	23716 KB	Output is correct
10	Correct	13 ms	23748 KB	Output is correct
11	Incorrect	13 ms	23724 KB	Wrong Answer[1]
12	Halted	0 ms	0 KB	-