| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 577382 |
2022-06-14T16:36:11 Z |
Noam527 |
Game (APIO22_game) |
C++17 |
|
1 ms |
208 KB |
#include <bits/stdc++.h>
#include "game.h"
const int OO = 0;
using namespace std;
int n, k;
vector<vector<int>> g, grev;
vector<int> s, e;
// s: maximum that reaches us
// e: minimum that we can reach
// e <= s, except for initial state
void init(int nn, int kk) {
n = nn;
k = kk;
g.resize(n);
grev.resize(n);
s.resize(n, -1);
e.resize(n, n);
for (int i = 0; i < k; i++) {
s[i] = i;
e[i] = i;
}
}
void forward_dfs(int l, int m, int r, int v, int reach) {
if (OO) {
cout << "forward: v, e, s = " << v << " " << e[v] << " " << s[v] << '\n';
}
if (!(l <= e[v] && s[v] < m)) return;
s[v] = reach;
for (const auto &i : g[v]) {
forward_dfs(l, m, r, i, reach);
}
}
void backward_dfs(int l, int m, int r, int v, int reach) {
if (OO) {
cout << "backward: v, e, s = " << v << " " << e[v] << " " << s[v] << '\n';
}
if (!(m < e[v] && s[v] <= r)) return;
e[v] = reach;
for (const auto &i : grev[v]) {
backward_dfs(l, m, r, i, reach);
}
}
int add(int layer, int l, int r, int u, int v) {
if (OO) {
cout << "on layer " << layer << " " << l << " " << r << '\n';
}
if (l > r) return 0;
int m = (l + r) / 2;
if (s[u] >= m && e[v] <= m) return 1;
if (s[u] >= m)
forward_dfs(l, m, r, v, s[u]);
if (e[v] <= m)
backward_dfs(l, m, r, u, e[v]);
if (s[u] > m || e[v] > m) {
if (add(layer + 1, m + 1, r, u, v)) return 1;
}
if (s[u] < m || e[v] < m) {
if (add(layer + 1, l, m - 1, u, v)) return 1;
}
return 0;
}
void brute_dfs(vector<int> &vis, int v) {
if (vis[v]) return;
vis[v] = 1;
for (const auto &i : g[v])
brute_dfs(vis, i);
}
int brute() {
vector<int> vis(n);
for (int i = 0; i < k; i++) {
for (auto &x : vis) x = 0;
for (const auto &j : g[i])
brute_dfs(vis, j);
for (int j = 0; j <= i; j++)
if (vis[j]) return 1;
}
return 0;
}
int add_teleporter(int u, int v) {
if (OO) {
cout << "current s: ";
for (const auto &i : s) cout << i << " "; cout << '\n';
cout << "current e: ";
for (const auto &i : e) cout << i << " "; cout << '\n';
}
/*
if (u < k && v < k) {
return u >= v;
}
*/
g[u].push_back(v);
grev[v].push_back(u);
int x = add(0, 0, k - 1, u, v);
if (OO) {
int y = brute();
if (x != y) {
cout << "difference! " << x << " " << y << '\n';
}
}
return x;
}
Compilation message
game.cpp: In function 'int add_teleporter(int, int)':
game.cpp:92:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
92 | for (const auto &i : s) cout << i << " "; cout << '\n';
| ^~~
game.cpp:92:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
92 | for (const auto &i : s) cout << i << " "; cout << '\n';
| ^~~~
game.cpp:94:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
94 | for (const auto &i : e) cout << i << " "; cout << '\n';
| ^~~
game.cpp:94:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
94 | for (const auto &i : e) cout << i << " "; cout << '\n';
| ^~~~
| # |
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 |
1 ms |
208 KB |
Output is correct |
| 4 |
Correct |
0 ms |
208 KB |
Output is correct |
| 5 |
Correct |
1 ms |
208 KB |
Output is correct |
| 6 |
Correct |
1 ms |
208 KB |
Output is correct |
| 7 |
Correct |
1 ms |
208 KB |
Output is correct |
| # |
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 |
1 ms |
208 KB |
Output is correct |
| 4 |
Correct |
0 ms |
208 KB |
Output is correct |
| 5 |
Correct |
1 ms |
208 KB |
Output is correct |
| 6 |
Correct |
1 ms |
208 KB |
Output is correct |
| 7 |
Correct |
1 ms |
208 KB |
Output is correct |
| 8 |
Correct |
0 ms |
208 KB |
Output is correct |
| 9 |
Correct |
0 ms |
208 KB |
Output is correct |
| 10 |
Correct |
0 ms |
208 KB |
Output is correct |
| 11 |
Correct |
0 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 |
208 KB |
Output is correct |
| 15 |
Correct |
0 ms |
208 KB |
Output is correct |
| 16 |
Correct |
1 ms |
208 KB |
Output is correct |
| 17 |
Incorrect |
1 ms |
208 KB |
Wrong Answer[1] |
| 18 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
1 ms |
208 KB |
Output is correct |
| 4 |
Correct |
0 ms |
208 KB |
Output is correct |
| 5 |
Correct |
1 ms |
208 KB |
Output is correct |
| 6 |
Correct |
1 ms |
208 KB |
Output is correct |
| 7 |
Correct |
1 ms |
208 KB |
Output is correct |
| 8 |
Correct |
0 ms |
208 KB |
Output is correct |
| 9 |
Correct |
0 ms |
208 KB |
Output is correct |
| 10 |
Correct |
0 ms |
208 KB |
Output is correct |
| 11 |
Correct |
0 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 |
208 KB |
Output is correct |
| 15 |
Correct |
0 ms |
208 KB |
Output is correct |
| 16 |
Correct |
1 ms |
208 KB |
Output is correct |
| 17 |
Incorrect |
1 ms |
208 KB |
Wrong Answer[1] |
| 18 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
1 ms |
208 KB |
Output is correct |
| 4 |
Correct |
0 ms |
208 KB |
Output is correct |
| 5 |
Correct |
1 ms |
208 KB |
Output is correct |
| 6 |
Correct |
1 ms |
208 KB |
Output is correct |
| 7 |
Correct |
1 ms |
208 KB |
Output is correct |
| 8 |
Correct |
0 ms |
208 KB |
Output is correct |
| 9 |
Correct |
0 ms |
208 KB |
Output is correct |
| 10 |
Correct |
0 ms |
208 KB |
Output is correct |
| 11 |
Correct |
0 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 |
208 KB |
Output is correct |
| 15 |
Correct |
0 ms |
208 KB |
Output is correct |
| 16 |
Correct |
1 ms |
208 KB |
Output is correct |
| 17 |
Incorrect |
1 ms |
208 KB |
Wrong Answer[1] |
| 18 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
1 ms |
208 KB |
Output is correct |
| 4 |
Correct |
0 ms |
208 KB |
Output is correct |
| 5 |
Correct |
1 ms |
208 KB |
Output is correct |
| 6 |
Correct |
1 ms |
208 KB |
Output is correct |
| 7 |
Correct |
1 ms |
208 KB |
Output is correct |
| 8 |
Correct |
0 ms |
208 KB |
Output is correct |
| 9 |
Correct |
0 ms |
208 KB |
Output is correct |
| 10 |
Correct |
0 ms |
208 KB |
Output is correct |
| 11 |
Correct |
0 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 |
208 KB |
Output is correct |
| 15 |
Correct |
0 ms |
208 KB |
Output is correct |
| 16 |
Correct |
1 ms |
208 KB |
Output is correct |
| 17 |
Incorrect |
1 ms |
208 KB |
Wrong Answer[1] |
| 18 |
Halted |
0 ms |
0 KB |
- |
