| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 983832 |
2024-05-16T07:06:37 Z |
vjudge1 |
Game (APIO22_game) |
C++17 |
|
4000 ms |
19188 KB |
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
const int N = 300300;
int n, k;
vector<int> g[N];
vector<int> rg[N];
int cmp[N];
int tin[N], tout[N], T = 0;
bool vis[N];
void precalc(int s) {
vis[s] = true;
tin[s] = T++;
for (int to : g[s]) if (!vis[to]) {
precalc(to);
}
tout[s] = T++;
}
void dfs(int s, int c) {
vis[s] = true;
cmp[s] = c;
for (int to : rg[s]) if (!vis[to]) {
dfs(to, c);
}
}
void init(int N, int K) {
n = N, k = K;
for (int i = 0; i < k - 1; i++) {
g[i].push_back(i + 1);
rg[i + 1].push_back(i);
}
}
int add_teleporter(int u, int v) {
if (u == v && u < k) return 1;
T = 0;
for (int i = 0; i < n; i++) {
cmp[i] = 0;
tin[i] = tout[i] = 0;
vis[i] = false;
}
g[u].push_back(v);
rg[v].push_back(u);
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
precalc(i);
}
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [](int x, int y) {
return tout[x] > tout[y];
});
for (int i = 0; i < n; i++) vis[i] = false;
int cnt = 1;
for (int c : ord) {
if (vis[c]) continue;
dfs(c, cnt++);
}
int sz[cnt] = {};
for (int i = 0; i < n; i++) {
sz[cmp[i]]++;
}
for (int i = 0; i < k; i++) {
if (sz[cmp[i]] > 1) {
return 1;
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
15960 KB |
Output is correct |
| 2 |
Correct |
5 ms |
18096 KB |
Output is correct |
| 3 |
Correct |
7 ms |
18164 KB |
Output is correct |
| 4 |
Correct |
4 ms |
18008 KB |
Output is correct |
| 5 |
Correct |
5 ms |
18008 KB |
Output is correct |
| 6 |
Correct |
4 ms |
18160 KB |
Output is correct |
| 7 |
Correct |
5 ms |
18008 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
15960 KB |
Output is correct |
| 2 |
Correct |
5 ms |
18096 KB |
Output is correct |
| 3 |
Correct |
7 ms |
18164 KB |
Output is correct |
| 4 |
Correct |
4 ms |
18008 KB |
Output is correct |
| 5 |
Correct |
5 ms |
18008 KB |
Output is correct |
| 6 |
Correct |
4 ms |
18160 KB |
Output is correct |
| 7 |
Correct |
5 ms |
18008 KB |
Output is correct |
| 8 |
Correct |
4 ms |
18008 KB |
Output is correct |
| 9 |
Correct |
5 ms |
16104 KB |
Output is correct |
| 10 |
Correct |
4 ms |
18008 KB |
Output is correct |
| 11 |
Correct |
5 ms |
18008 KB |
Output is correct |
| 12 |
Correct |
5 ms |
18008 KB |
Output is correct |
| 13 |
Correct |
5 ms |
18076 KB |
Output is correct |
| 14 |
Correct |
5 ms |
18100 KB |
Output is correct |
| 15 |
Correct |
5 ms |
18052 KB |
Output is correct |
| 16 |
Correct |
6 ms |
18264 KB |
Output is correct |
| 17 |
Correct |
5 ms |
18164 KB |
Output is correct |
| 18 |
Correct |
4 ms |
18100 KB |
Output is correct |
| 19 |
Correct |
4 ms |
18008 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
15960 KB |
Output is correct |
| 2 |
Correct |
5 ms |
18096 KB |
Output is correct |
| 3 |
Correct |
7 ms |
18164 KB |
Output is correct |
| 4 |
Correct |
4 ms |
18008 KB |
Output is correct |
| 5 |
Correct |
5 ms |
18008 KB |
Output is correct |
| 6 |
Correct |
4 ms |
18160 KB |
Output is correct |
| 7 |
Correct |
5 ms |
18008 KB |
Output is correct |
| 8 |
Correct |
4 ms |
18008 KB |
Output is correct |
| 9 |
Correct |
5 ms |
16104 KB |
Output is correct |
| 10 |
Correct |
4 ms |
18008 KB |
Output is correct |
| 11 |
Correct |
5 ms |
18008 KB |
Output is correct |
| 12 |
Correct |
5 ms |
18008 KB |
Output is correct |
| 13 |
Correct |
5 ms |
18076 KB |
Output is correct |
| 14 |
Correct |
5 ms |
18100 KB |
Output is correct |
| 15 |
Correct |
5 ms |
18052 KB |
Output is correct |
| 16 |
Correct |
6 ms |
18264 KB |
Output is correct |
| 17 |
Correct |
5 ms |
18164 KB |
Output is correct |
| 18 |
Correct |
4 ms |
18100 KB |
Output is correct |
| 19 |
Correct |
4 ms |
18008 KB |
Output is correct |
| 20 |
Correct |
38 ms |
18008 KB |
Output is correct |
| 21 |
Correct |
8 ms |
18008 KB |
Output is correct |
| 22 |
Correct |
40 ms |
18224 KB |
Output is correct |
| 23 |
Correct |
49 ms |
18008 KB |
Output is correct |
| 24 |
Correct |
39 ms |
18268 KB |
Output is correct |
| 25 |
Correct |
199 ms |
18256 KB |
Output is correct |
| 26 |
Correct |
265 ms |
18512 KB |
Output is correct |
| 27 |
Correct |
186 ms |
18264 KB |
Output is correct |
| 28 |
Correct |
76 ms |
18280 KB |
Output is correct |
| 29 |
Correct |
154 ms |
18736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
15960 KB |
Output is correct |
| 2 |
Correct |
5 ms |
18096 KB |
Output is correct |
| 3 |
Correct |
7 ms |
18164 KB |
Output is correct |
| 4 |
Correct |
4 ms |
18008 KB |
Output is correct |
| 5 |
Correct |
5 ms |
18008 KB |
Output is correct |
| 6 |
Correct |
4 ms |
18160 KB |
Output is correct |
| 7 |
Correct |
5 ms |
18008 KB |
Output is correct |
| 8 |
Correct |
4 ms |
18008 KB |
Output is correct |
| 9 |
Correct |
5 ms |
16104 KB |
Output is correct |
| 10 |
Correct |
4 ms |
18008 KB |
Output is correct |
| 11 |
Correct |
5 ms |
18008 KB |
Output is correct |
| 12 |
Correct |
5 ms |
18008 KB |
Output is correct |
| 13 |
Correct |
5 ms |
18076 KB |
Output is correct |
| 14 |
Correct |
5 ms |
18100 KB |
Output is correct |
| 15 |
Correct |
5 ms |
18052 KB |
Output is correct |
| 16 |
Correct |
6 ms |
18264 KB |
Output is correct |
| 17 |
Correct |
5 ms |
18164 KB |
Output is correct |
| 18 |
Correct |
4 ms |
18100 KB |
Output is correct |
| 19 |
Correct |
4 ms |
18008 KB |
Output is correct |
| 20 |
Correct |
38 ms |
18008 KB |
Output is correct |
| 21 |
Correct |
8 ms |
18008 KB |
Output is correct |
| 22 |
Correct |
40 ms |
18224 KB |
Output is correct |
| 23 |
Correct |
49 ms |
18008 KB |
Output is correct |
| 24 |
Correct |
39 ms |
18268 KB |
Output is correct |
| 25 |
Correct |
199 ms |
18256 KB |
Output is correct |
| 26 |
Correct |
265 ms |
18512 KB |
Output is correct |
| 27 |
Correct |
186 ms |
18264 KB |
Output is correct |
| 28 |
Correct |
76 ms |
18280 KB |
Output is correct |
| 29 |
Correct |
154 ms |
18736 KB |
Output is correct |
| 30 |
Execution timed out |
4086 ms |
19188 KB |
Time limit exceeded |
| 31 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
15960 KB |
Output is correct |
| 2 |
Correct |
5 ms |
18096 KB |
Output is correct |
| 3 |
Correct |
7 ms |
18164 KB |
Output is correct |
| 4 |
Correct |
4 ms |
18008 KB |
Output is correct |
| 5 |
Correct |
5 ms |
18008 KB |
Output is correct |
| 6 |
Correct |
4 ms |
18160 KB |
Output is correct |
| 7 |
Correct |
5 ms |
18008 KB |
Output is correct |
| 8 |
Correct |
4 ms |
18008 KB |
Output is correct |
| 9 |
Correct |
5 ms |
16104 KB |
Output is correct |
| 10 |
Correct |
4 ms |
18008 KB |
Output is correct |
| 11 |
Correct |
5 ms |
18008 KB |
Output is correct |
| 12 |
Correct |
5 ms |
18008 KB |
Output is correct |
| 13 |
Correct |
5 ms |
18076 KB |
Output is correct |
| 14 |
Correct |
5 ms |
18100 KB |
Output is correct |
| 15 |
Correct |
5 ms |
18052 KB |
Output is correct |
| 16 |
Correct |
6 ms |
18264 KB |
Output is correct |
| 17 |
Correct |
5 ms |
18164 KB |
Output is correct |
| 18 |
Correct |
4 ms |
18100 KB |
Output is correct |
| 19 |
Correct |
4 ms |
18008 KB |
Output is correct |
| 20 |
Correct |
38 ms |
18008 KB |
Output is correct |
| 21 |
Correct |
8 ms |
18008 KB |
Output is correct |
| 22 |
Correct |
40 ms |
18224 KB |
Output is correct |
| 23 |
Correct |
49 ms |
18008 KB |
Output is correct |
| 24 |
Correct |
39 ms |
18268 KB |
Output is correct |
| 25 |
Correct |
199 ms |
18256 KB |
Output is correct |
| 26 |
Correct |
265 ms |
18512 KB |
Output is correct |
| 27 |
Correct |
186 ms |
18264 KB |
Output is correct |
| 28 |
Correct |
76 ms |
18280 KB |
Output is correct |
| 29 |
Correct |
154 ms |
18736 KB |
Output is correct |
| 30 |
Execution timed out |
4086 ms |
19188 KB |
Time limit exceeded |
| 31 |
Halted |
0 ms |
0 KB |
- |
