#ifndef Nhoksocqt1
#include "game.h"
#endif // Nhoksocqt1
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
template<class X, class Y>
inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}
mt19937 rng(2);
//#define HAHA
int Random(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const int MAXN = 300005;
const int MAXM = 800005;
vector<int> adj[MAXN], adjr[MAXN];
int min_bucket_to[MAXN][20], max_bucket_from[MAXN][20];
int id_bucket[MAXN], min_same[MAXN], min_spe_to[MAXN], max_spe_from[MAXN];
int numBlock, maxLog, numNode, numSpecial;
bool inQuMax[MAXN], inQuMin[MAXN], dx[MAXN];
void init(int _N, int _K) {
numNode = _N, numSpecial = _K;
maxLog = 31 - __builtin_clz(numSpecial);
for (int i = 0; i < numNode; ++i) {
if(i < numSpecial) {
min_spe_to[i] = max_spe_from[i] = i;
for (int j = 0; j <= maxLog; ++j)
min_bucket_to[i][j] = max_bucket_from[i][j] = i >> j & 1;
id_bucket[i] = i;
min_same[i] = 0;
} else {
max_spe_from[i] = -1;
min_same[i] = maxLog + 1;
min_spe_to[i] = numSpecial;
for (int j = 0; j <= maxLog; ++j)
min_bucket_to[i][j] = 2, max_bucket_from[i][j] = -1;
}
}
}
bool brute(int u, int v) {
queue<int> qu;
if(min_spe_to[u] > min(min_spe_to[v], v)) {
min_spe_to[u] = min(min_spe_to[v], v);
qu.push(u);
}
while(sz(qu)) {
int u(qu.front()); qu.pop();
if(max_spe_from[u] >= min_spe_to[u])
return true;
for (int it = 0; it < sz(adjr[u]); ++it) {
int v(adjr[u][it]);
if(min_spe_to[v] > min_spe_to[u]) {
min_spe_to[v] = min_spe_to[u];
qu.push(v);
}
}
}
int max_spe_from_now = max(max_spe_from[u], (u < numSpecial ? u : -1));
if(max_spe_from[v] < max_spe_from_now) {
max_spe_from[v] = max_spe_from_now;
qu.push(v);
}
while(sz(qu)) {
int u(qu.front()); qu.pop();
if(u >= numSpecial && max_spe_from[u] >= min_spe_to[u])
return true;
for (int it = 0; it < sz(adj[u]); ++it) {
int v(adj[u][it]);
if(max_spe_from[v] < max_spe_from[u]) {
max_spe_from[v] = max_spe_from[u];
qu.push(v);
}
}
}
return false;
}
bool magicFunc(int u, int v) {
queue<int> quMax, quMin;
for (int k = maxLog; k >= 0; --k) {
if(max(min_same[u], min_same[v]) <= k + 1 && (id_bucket[u] >> (k + 1)) == (id_bucket[v] >> (k + 1))) {
if(min_bucket_to[u][k] > min_bucket_to[v][k]) {
min_bucket_to[u][k] = min_bucket_to[v][k];
if(!inQuMin[u]) {
quMin.push(u);
inQuMin[u] = 1;
}
}
if(max_bucket_from[v][k] < max_bucket_from[u][k]) {
max_bucket_from[v][k] = max_bucket_from[u][k];
if(!inQuMax[v]) {
quMax.push(v);
inQuMax[v] = 1;
}
}
}
vector<int> nodes;
while(sz(quMin)) {
int u(quMin.front()); quMin.pop();
inQuMin[u] = 0;
if(max_bucket_from[u][k] > min_bucket_to[u][k])
return true;
if(max_bucket_from[u][k] == min_bucket_to[u][k]) {
id_bucket[u] |= (max_bucket_from[u][k] << k);
min_same[u] = min(min_same[u], k);
if(k == 0)
return true;
if(!dx[u]) {
nodes.push_back(u);
dx[u] = 1;
}
}
//cout << "MIN BUCKET " << k << " TO " << u << ' ' << min_same[u] << ' ' << min_bucket_to[u][k] << '\n';
for (int it = 0; it < sz(adjr[u]); ++it) {
int v(adjr[u][it]);
if(min_same[v] > k + 1 || (id_bucket[u] >> (k + 1)) != (id_bucket[v] >> (k + 1)))
continue;
if(min_bucket_to[v][k] > min_bucket_to[u][k]) {
min_bucket_to[v][k] = min_bucket_to[u][k];
if(!inQuMin[v]) {
quMin.push(v);
inQuMin[v] = 1;
}
}
}
}
while(sz(quMax)) {
int u(quMax.front()); quMax.pop();
inQuMax[u] = 0;
//cout << "MAX BUCKET " << k << " FROM " << u << ' ' << min_same[u] << ' ' << max_bucket_from[u][k] << '\n';
if(max_bucket_from[u][k] > min_bucket_to[u][k])
return true;
if(max_bucket_from[u][k] == min_bucket_to[u][k]) {
id_bucket[u] |= (max_bucket_from[u][k] << k);
min_same[u] = min(min_same[u], k);
if(k == 0)
return true;
if(!dx[u]) {
nodes.push_back(u);
dx[u] = 1;
}
}
for (int it = 0; it < sz(adj[u]); ++it) {
int v(adj[u][it]);
if(min_same[v] > k + 1 || (id_bucket[u] >> (k + 1)) != (id_bucket[v] >> (k + 1)))
continue;
if(max_bucket_from[v][k] < max_bucket_from[u][k]) {
max_bucket_from[v][k] = max_bucket_from[u][k];
if(!inQuMax[v]) {
quMax.push(v);
inQuMax[v] = 1;
}
}
}
}
for (int it = 0; it < sz(nodes); ++it) {
int u(nodes[it]);
dx[u] = 0;
//cout << u << ' ' << min_same[u] << ' ' << id_bucket[u] << ":\n";
for (int it = 0; it < sz(adj[u]); ++it) {
int v(adj[u][it]);
//cout << v << ' ' << min_same[v] << ' ' << id_bucket[v] << ' ' << (id_bucket[v] >> k) << ' ' << (id_bucket[u] >> k) << '\n';
if(max(min_same[u], min_same[v]) > k || (id_bucket[u] >> k) != (id_bucket[v] >> k))
continue;
if(min_bucket_to[u][k - 1] > min_bucket_to[v][k - 1]) {
min_bucket_to[u][k - 1] = min_bucket_to[v][k - 1];
if(!inQuMin[u]) {
quMin.push(u);
inQuMin[u] = 1;
}
}
}
for (int it = 0; it < sz(adjr[u]); ++it) {
int v(adjr[u][it]);
if(max(min_same[u], min_same[v]) > k || (id_bucket[u] >> k) != (id_bucket[v] >> k))
continue;
if(max_bucket_from[u][k - 1] < max_bucket_from[v][k - 1]) {
max_bucket_from[u][k - 1] = max_bucket_from[v][k - 1];
if(!inQuMax[u]) {
quMax.push(u);
inQuMax[u] = 1;
}
}
}
}
}
return false;
}
int add_teleporter(int u, int v) {
if(max(u, v) < numSpecial)
return (u >= v);
if(u == v)
return false;
adj[u].push_back(v);
adjr[v].push_back(u);
//cout << brute(u, v) << ' ' << magicFunc(u, v) << '\n'; return false;
/*if(numNode <= 30000 && numSpecial <= 1000) {
return brute(u, v);
} else*/ {
return magicFunc(u, v);
}
return false;
}
#ifdef Nhoksocqt1
int main(void) {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define TASK "game"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
int n, k, m;
cin >> n >> k >> m;
init(n, k);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
//u = Random(0, n - 2), v = Random(max(k, u + 1), n - 1); if(Random(0, 1)) swap(u, v);
int ans = add_teleporter(u, v);
cout << "ANSWER FOR EDGE " << u << " TO " << v << ": " << ans << '\n';
if(ans == 1)
break;
}
return 0;
}
#endif // Nhoksocqt1
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
23640 KB |
Output is correct |
2 |
Correct |
5 ms |
23640 KB |
Output is correct |
3 |
Correct |
5 ms |
23640 KB |
Output is correct |
4 |
Correct |
5 ms |
23640 KB |
Output is correct |
5 |
Correct |
5 ms |
23640 KB |
Output is correct |
6 |
Correct |
5 ms |
23640 KB |
Output is correct |
7 |
Correct |
6 ms |
23640 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
23640 KB |
Output is correct |
2 |
Correct |
5 ms |
23640 KB |
Output is correct |
3 |
Correct |
5 ms |
23640 KB |
Output is correct |
4 |
Correct |
5 ms |
23640 KB |
Output is correct |
5 |
Correct |
5 ms |
23640 KB |
Output is correct |
6 |
Correct |
5 ms |
23640 KB |
Output is correct |
7 |
Correct |
6 ms |
23640 KB |
Output is correct |
8 |
Correct |
5 ms |
23640 KB |
Output is correct |
9 |
Correct |
5 ms |
23640 KB |
Output is correct |
10 |
Correct |
6 ms |
23640 KB |
Output is correct |
11 |
Correct |
6 ms |
23640 KB |
Output is correct |
12 |
Correct |
5 ms |
23640 KB |
Output is correct |
13 |
Correct |
5 ms |
23640 KB |
Output is correct |
14 |
Correct |
5 ms |
23640 KB |
Output is correct |
15 |
Correct |
5 ms |
23640 KB |
Output is correct |
16 |
Correct |
5 ms |
23640 KB |
Output is correct |
17 |
Correct |
6 ms |
23896 KB |
Output is correct |
18 |
Correct |
5 ms |
23784 KB |
Output is correct |
19 |
Correct |
5 ms |
23640 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
23640 KB |
Output is correct |
2 |
Correct |
5 ms |
23640 KB |
Output is correct |
3 |
Correct |
5 ms |
23640 KB |
Output is correct |
4 |
Correct |
5 ms |
23640 KB |
Output is correct |
5 |
Correct |
5 ms |
23640 KB |
Output is correct |
6 |
Correct |
5 ms |
23640 KB |
Output is correct |
7 |
Correct |
6 ms |
23640 KB |
Output is correct |
8 |
Correct |
5 ms |
23640 KB |
Output is correct |
9 |
Correct |
5 ms |
23640 KB |
Output is correct |
10 |
Correct |
6 ms |
23640 KB |
Output is correct |
11 |
Correct |
6 ms |
23640 KB |
Output is correct |
12 |
Correct |
5 ms |
23640 KB |
Output is correct |
13 |
Correct |
5 ms |
23640 KB |
Output is correct |
14 |
Correct |
5 ms |
23640 KB |
Output is correct |
15 |
Correct |
5 ms |
23640 KB |
Output is correct |
16 |
Correct |
5 ms |
23640 KB |
Output is correct |
17 |
Correct |
6 ms |
23896 KB |
Output is correct |
18 |
Correct |
5 ms |
23784 KB |
Output is correct |
19 |
Correct |
5 ms |
23640 KB |
Output is correct |
20 |
Correct |
5 ms |
23640 KB |
Output is correct |
21 |
Correct |
5 ms |
23640 KB |
Output is correct |
22 |
Correct |
5 ms |
23640 KB |
Output is correct |
23 |
Correct |
6 ms |
23640 KB |
Output is correct |
24 |
Correct |
6 ms |
23640 KB |
Output is correct |
25 |
Correct |
7 ms |
24152 KB |
Output is correct |
26 |
Correct |
9 ms |
24316 KB |
Output is correct |
27 |
Correct |
8 ms |
23896 KB |
Output is correct |
28 |
Correct |
6 ms |
23640 KB |
Output is correct |
29 |
Correct |
6 ms |
23640 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
23640 KB |
Output is correct |
2 |
Correct |
5 ms |
23640 KB |
Output is correct |
3 |
Correct |
5 ms |
23640 KB |
Output is correct |
4 |
Correct |
5 ms |
23640 KB |
Output is correct |
5 |
Correct |
5 ms |
23640 KB |
Output is correct |
6 |
Correct |
5 ms |
23640 KB |
Output is correct |
7 |
Correct |
6 ms |
23640 KB |
Output is correct |
8 |
Correct |
5 ms |
23640 KB |
Output is correct |
9 |
Correct |
5 ms |
23640 KB |
Output is correct |
10 |
Correct |
6 ms |
23640 KB |
Output is correct |
11 |
Correct |
6 ms |
23640 KB |
Output is correct |
12 |
Correct |
5 ms |
23640 KB |
Output is correct |
13 |
Correct |
5 ms |
23640 KB |
Output is correct |
14 |
Correct |
5 ms |
23640 KB |
Output is correct |
15 |
Correct |
5 ms |
23640 KB |
Output is correct |
16 |
Correct |
5 ms |
23640 KB |
Output is correct |
17 |
Correct |
6 ms |
23896 KB |
Output is correct |
18 |
Correct |
5 ms |
23784 KB |
Output is correct |
19 |
Correct |
5 ms |
23640 KB |
Output is correct |
20 |
Correct |
5 ms |
23640 KB |
Output is correct |
21 |
Correct |
5 ms |
23640 KB |
Output is correct |
22 |
Correct |
5 ms |
23640 KB |
Output is correct |
23 |
Correct |
6 ms |
23640 KB |
Output is correct |
24 |
Correct |
6 ms |
23640 KB |
Output is correct |
25 |
Correct |
7 ms |
24152 KB |
Output is correct |
26 |
Correct |
9 ms |
24316 KB |
Output is correct |
27 |
Correct |
8 ms |
23896 KB |
Output is correct |
28 |
Correct |
6 ms |
23640 KB |
Output is correct |
29 |
Correct |
6 ms |
23640 KB |
Output is correct |
30 |
Correct |
26 ms |
29384 KB |
Output is correct |
31 |
Correct |
11 ms |
28760 KB |
Output is correct |
32 |
Correct |
37 ms |
30388 KB |
Output is correct |
33 |
Correct |
34 ms |
30424 KB |
Output is correct |
34 |
Correct |
68 ms |
30696 KB |
Output is correct |
35 |
Correct |
52 ms |
30212 KB |
Output is correct |
36 |
Correct |
74 ms |
30020 KB |
Output is correct |
37 |
Correct |
65 ms |
30288 KB |
Output is correct |
38 |
Correct |
56 ms |
30128 KB |
Output is correct |
39 |
Correct |
51 ms |
29908 KB |
Output is correct |
40 |
Correct |
75 ms |
30728 KB |
Output is correct |
41 |
Correct |
53 ms |
30012 KB |
Output is correct |
42 |
Correct |
49 ms |
30228 KB |
Output is correct |
43 |
Correct |
72 ms |
30140 KB |
Output is correct |
44 |
Correct |
72 ms |
30936 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
23640 KB |
Output is correct |
2 |
Correct |
5 ms |
23640 KB |
Output is correct |
3 |
Correct |
5 ms |
23640 KB |
Output is correct |
4 |
Correct |
5 ms |
23640 KB |
Output is correct |
5 |
Correct |
5 ms |
23640 KB |
Output is correct |
6 |
Correct |
5 ms |
23640 KB |
Output is correct |
7 |
Correct |
6 ms |
23640 KB |
Output is correct |
8 |
Correct |
5 ms |
23640 KB |
Output is correct |
9 |
Correct |
5 ms |
23640 KB |
Output is correct |
10 |
Correct |
6 ms |
23640 KB |
Output is correct |
11 |
Correct |
6 ms |
23640 KB |
Output is correct |
12 |
Correct |
5 ms |
23640 KB |
Output is correct |
13 |
Correct |
5 ms |
23640 KB |
Output is correct |
14 |
Correct |
5 ms |
23640 KB |
Output is correct |
15 |
Correct |
5 ms |
23640 KB |
Output is correct |
16 |
Correct |
5 ms |
23640 KB |
Output is correct |
17 |
Correct |
6 ms |
23896 KB |
Output is correct |
18 |
Correct |
5 ms |
23784 KB |
Output is correct |
19 |
Correct |
5 ms |
23640 KB |
Output is correct |
20 |
Correct |
5 ms |
23640 KB |
Output is correct |
21 |
Correct |
5 ms |
23640 KB |
Output is correct |
22 |
Correct |
5 ms |
23640 KB |
Output is correct |
23 |
Correct |
6 ms |
23640 KB |
Output is correct |
24 |
Correct |
6 ms |
23640 KB |
Output is correct |
25 |
Correct |
7 ms |
24152 KB |
Output is correct |
26 |
Correct |
9 ms |
24316 KB |
Output is correct |
27 |
Correct |
8 ms |
23896 KB |
Output is correct |
28 |
Correct |
6 ms |
23640 KB |
Output is correct |
29 |
Correct |
6 ms |
23640 KB |
Output is correct |
30 |
Correct |
26 ms |
29384 KB |
Output is correct |
31 |
Correct |
11 ms |
28760 KB |
Output is correct |
32 |
Correct |
37 ms |
30388 KB |
Output is correct |
33 |
Correct |
34 ms |
30424 KB |
Output is correct |
34 |
Correct |
68 ms |
30696 KB |
Output is correct |
35 |
Correct |
52 ms |
30212 KB |
Output is correct |
36 |
Correct |
74 ms |
30020 KB |
Output is correct |
37 |
Correct |
65 ms |
30288 KB |
Output is correct |
38 |
Correct |
56 ms |
30128 KB |
Output is correct |
39 |
Correct |
51 ms |
29908 KB |
Output is correct |
40 |
Correct |
75 ms |
30728 KB |
Output is correct |
41 |
Correct |
53 ms |
30012 KB |
Output is correct |
42 |
Correct |
49 ms |
30228 KB |
Output is correct |
43 |
Correct |
72 ms |
30140 KB |
Output is correct |
44 |
Correct |
72 ms |
30936 KB |
Output is correct |
45 |
Correct |
301 ms |
78688 KB |
Output is correct |
46 |
Correct |
21 ms |
68184 KB |
Output is correct |
47 |
Correct |
18 ms |
67416 KB |
Output is correct |
48 |
Correct |
498 ms |
87184 KB |
Output is correct |
49 |
Correct |
323 ms |
86116 KB |
Output is correct |
50 |
Correct |
1906 ms |
84576 KB |
Output is correct |
51 |
Correct |
1588 ms |
86788 KB |
Output is correct |
52 |
Correct |
916 ms |
86060 KB |
Output is correct |
53 |
Correct |
1413 ms |
86444 KB |
Output is correct |
54 |
Correct |
1635 ms |
85668 KB |
Output is correct |
55 |
Correct |
2481 ms |
89280 KB |
Output is correct |
56 |
Correct |
3351 ms |
88688 KB |
Output is correct |
57 |
Correct |
808 ms |
80044 KB |
Output is correct |
58 |
Correct |
896 ms |
80100 KB |
Output is correct |
59 |
Correct |
828 ms |
80168 KB |
Output is correct |
60 |
Correct |
1268 ms |
81752 KB |
Output is correct |
61 |
Correct |
1720 ms |
81392 KB |
Output is correct |
62 |
Correct |
1122 ms |
81652 KB |
Output is correct |
63 |
Correct |
994 ms |
78484 KB |
Output is correct |
64 |
Correct |
2881 ms |
88332 KB |
Output is correct |
65 |
Correct |
842 ms |
82608 KB |
Output is correct |
66 |
Correct |
656 ms |
78436 KB |
Output is correct |
67 |
Correct |
1270 ms |
86944 KB |
Output is correct |
68 |
Correct |
273 ms |
76840 KB |
Output is correct |
69 |
Correct |
82 ms |
71044 KB |
Output is correct |
70 |
Correct |
1223 ms |
83764 KB |
Output is correct |
71 |
Correct |
403 ms |
79172 KB |
Output is correct |
72 |
Correct |
299 ms |
75292 KB |
Output is correct |
73 |
Correct |
906 ms |
83128 KB |
Output is correct |
74 |
Correct |
3884 ms |
88800 KB |
Output is correct |
75 |
Correct |
2013 ms |
87676 KB |
Output is correct |
76 |
Correct |
3393 ms |
87432 KB |
Output is correct |