#include <bits/stdc++.h>
#include "game.h"
const int OO = 0;
using namespace std;
int getbits(int cnt) {
return (1 << cnt) - 1;
}
void printbits(int v, int layers = 10) {
for (int i = 0; i < layers; i++)
cout << (v >> i & 1);
cout << endl;
}
int n, k;
vector<vector<int>> g, grev;
vector<int> s, e;
void initial_colors(int layer, int l, int r) {
if (l >= r) return;
int mid = (l + r) / 2;
for (int i = mid + 1; i <= r; i++)
s[i] |= 1 << layer, e[i] |= 1 << layer;
s[mid] |= 1 << layer;
initial_colors(layer + 1, l, mid - 1);
initial_colors(layer + 1, mid + 1, r);
}
void init(int nn, int kk) {
n = nn;
k = kk;
g.resize(n);
grev.resize(n);
s.resize(n);
e.resize(n);
initial_colors(0, 0, k - 1);
int layers = 1;
while (getbits(layers) < k) layers++;
for (int i = k; i < n; i++)
e[i] = getbits(layers);
if (OO) {
cout << "initial colors:\n";
for (int i = 0; i < n; i++) {
cout << i << '\n';
printbits(s[i]);
printbits(e[i]);
}
}
}
void forward_dfs(int layer, int smask, int emask, int v) {
if ((s[v] & smask) != smask || (e[v] & emask) != 0) return;
if (s[v] & (1 << layer)) return;
s[v] |= 1 << layer;
for (const auto &w : g[v])
forward_dfs(layer, smask, emask, w);
}
void backward_dfs(int layer, int smask, int emask, int v) {
if ((s[v] & smask) != smask || (e[v] & emask) != 0) return;
if (~e[v] & (1 << layer)) return;
e[v] ^= 1 << layer;
for (const auto &w : grev[v])
backward_dfs(layer, smask, emask, w);
}
int add(int layer, int smask, int emask, int l, int r, int u, int v) {
if (OO) {
cout << "starting layer " << layer << " " << l << " " << r << '\n';
printbits(s[u]);
printbits(e[v]);
}
if (l >= r) return 0;
if ((s[u] & (1 << layer)) && (~e[v] & (1 << layer))) return 1;
if (s[u] & (1 << layer)) {
// forward dfs
forward_dfs(layer, smask, emask, v);
}
if (~e[v] & (1 << layer)) {
// backward dfs
backward_dfs(layer, smask, emask, u);
}
int mid = (l + r) / 2;
if (s[u] & (1 << layer)) {
// return with added smask
return add(layer + 1, smask | (1 << layer), emask, l, mid - 1, u, v);
}
else if (~e[v] & (1 << layer)) {
// return with added emask
return add(layer + 1, smask, emask | (1 << layer), mid + 1, r, u, v);
}
return 0;
}
int add_teleporter(int u, int v) {
if (u < k && v < k) {
return u >= v;
}
g[u].push_back(v);
grev[v].push_back(u);
return add(0, 0, 0, 0, k - 1, u, v);
}
| # |
결과 |
실행 시간 |
메모리 |
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 |
0 ms |
208 KB |
Output is correct |
| 6 |
Correct |
0 ms |
208 KB |
Output is correct |
| 7 |
Correct |
1 ms |
208 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
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 |
0 ms |
208 KB |
Output is correct |
| 6 |
Correct |
0 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 |
1 ms |
308 KB |
Output is correct |
| 12 |
Correct |
0 ms |
208 KB |
Output is correct |
| 13 |
Incorrect |
0 ms |
208 KB |
Wrong Answer[1] |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
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 |
0 ms |
208 KB |
Output is correct |
| 6 |
Correct |
0 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 |
1 ms |
308 KB |
Output is correct |
| 12 |
Correct |
0 ms |
208 KB |
Output is correct |
| 13 |
Incorrect |
0 ms |
208 KB |
Wrong Answer[1] |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
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 |
0 ms |
208 KB |
Output is correct |
| 6 |
Correct |
0 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 |
1 ms |
308 KB |
Output is correct |
| 12 |
Correct |
0 ms |
208 KB |
Output is correct |
| 13 |
Incorrect |
0 ms |
208 KB |
Wrong Answer[1] |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
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 |
0 ms |
208 KB |
Output is correct |
| 6 |
Correct |
0 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 |
1 ms |
308 KB |
Output is correct |
| 12 |
Correct |
0 ms |
208 KB |
Output is correct |
| 13 |
Incorrect |
0 ms |
208 KB |
Wrong Answer[1] |
| 14 |
Halted |
0 ms |
0 KB |
- |
