#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;
const int BLOCK = 550;
vector<int> adj[MAXN], adjr[MAXN];
int min_bucket_to[MAXN], max_bucket_from[MAXN], min_spe_to[MAXN], max_spe_from[MAXN];
int id_block[MAXN], numBlock, numNode, numSpecial;
bool dx[MAXN];
void init(int _N, int _K) {
numNode = _N, numSpecial = _K;
for (int i = 0; i < numNode; ++i) {
min_spe_to[i] = (i < numSpecial) ? i : numSpecial;
max_spe_from[i] = (i < numSpecial) ? i : -1;
}
numBlock = (numSpecial + BLOCK - 1) / BLOCK;
for (int i = 0; i < numBlock; ++i) {
int L = i * BLOCK, R = min(numSpecial, (i + 1) * BLOCK - 1);
for (int j = L; j <= R; ++j) {
min_bucket_to[j] = max_bucket_from[j] = i;
id_block[j] = i;
}
}
for (int i = numSpecial; i < numNode; ++i) {
max_bucket_from[i] = -1;
min_bucket_to[i] = numBlock;
}
}
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> qu;
if(min_bucket_to[u] > min_bucket_to[v]) {
min_bucket_to[u] = min_bucket_to[v];
qu.push(u);
}
vector<int> nodes;
if(max_bucket_from[u] == min_bucket_to[u] && max_bucket_from[v] == min_bucket_to[v] && max_bucket_from[u] == max_bucket_from[v]) {
if(min_spe_to[u] > min_spe_to[v]) {
min_spe_to[u] = min_spe_to[v];
nodes.push_back(u);
} else
if(min_spe_to[v] > min_spe_to[u]) {
min_spe_to[v] = min_spe_to[u];
nodes.push_back(v);
}
if(max_spe_from[u] < max_spe_from[v]) {
max_spe_from[u] = max_spe_from[v];
nodes.push_back(u);
} else
if(max_spe_from[v] < max_spe_from[u]) {
max_spe_from[v] = max_spe_from[u];
nodes.push_back(v);
}
}
while(sz(qu)) {
int u(qu.front()); qu.pop();
//cout << "MIN BUCKET TO " << u << ' ' << min_bucket_to[u] << '\n';
if(max_bucket_from[u] > min_bucket_to[u])
return true;
bool checku = (max_bucket_from[u] == min_bucket_to[u]);
for (int it = 0; it < sz(adjr[u]); ++it) {
int v(adjr[u][it]);
if(max_bucket_from[v] == min_bucket_to[v] && checku && max_bucket_from[u] == max_bucket_from[v] && min_spe_to[v] > min_spe_to[u]) {
min_spe_to[v] = min_spe_to[u];
nodes.push_back(v);
}
if(min_bucket_to[v] > min_bucket_to[u]) {
min_bucket_to[v] = min_bucket_to[u];
qu.push(v);
}
}
}
if(max_bucket_from[v] < max_bucket_from[u]) {
max_bucket_from[v] = max_bucket_from[u];
qu.push(v);
}
while(sz(qu)) {
int u(qu.front()); qu.pop();
//cout << "MAX BUCKET FROM " << u << ' ' << max_bucket_from[u] << '\n';
if(max_bucket_from[u] > min_bucket_to[u])
return true;
bool checku = (max_bucket_from[u] == min_bucket_to[u]);
for (int it = 0; it < sz(adj[u]); ++it) {
int v(adj[u][it]);
if(max_bucket_from[v] == min_bucket_to[v] && checku && max_bucket_from[u] == max_bucket_from[v] && max_spe_from[v] < max_spe_from[u]) {
max_spe_from[v] = max_spe_from[u];
nodes.push_back(v);
}
if(max_bucket_from[v] < max_bucket_from[u]) {
max_bucket_from[v] = max_bucket_from[u];
qu.push(v);
}
}
}
for (int it = 0; it < sz(nodes); ++it)
qu.push(nodes[it]);
while(sz(qu)) {
int u(qu.front()); qu.pop();
//cout << "MIN SPE TO " << u << ' ' << min_spe_to[u] << '\n';
//cout << "MAX SPE FROM " << u << ' ' << max_spe_from[u] << '\n';
if(u >= numSpecial && 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(max_bucket_from[v] == min_bucket_to[v] && max_bucket_from[u] == max_bucket_from[v] && min_spe_to[v] > min_spe_to[u]) {
min_spe_to[v] = min_spe_to[u];
qu.push(v);
}
}
for (int it = 0; it < sz(adj[u]); ++it) {
int v(adj[u][it]);
if(max_bucket_from[v] == min_bucket_to[v] && max_bucket_from[u] == max_bucket_from[v] && max_spe_from[v] < max_spe_from[u]) {
max_spe_from[v] = max_spe_from[u];
qu.push(v);
}
}
}
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);
/*
#ifdef Nhoksocqt1
#ifdef HAHA
return brute(u, v);
#else
return magicFunc(u, v);
#endif // HAHA
#endif // Nhoksocqt1
*/
//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 |
20312 KB |
Output is correct |
2 |
Correct |
5 ms |
20312 KB |
Output is correct |
3 |
Correct |
5 ms |
20308 KB |
Output is correct |
4 |
Correct |
5 ms |
20564 KB |
Output is correct |
5 |
Correct |
5 ms |
20312 KB |
Output is correct |
6 |
Correct |
4 ms |
20312 KB |
Output is correct |
7 |
Correct |
4 ms |
20312 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
20312 KB |
Output is correct |
2 |
Correct |
5 ms |
20312 KB |
Output is correct |
3 |
Correct |
5 ms |
20308 KB |
Output is correct |
4 |
Correct |
5 ms |
20564 KB |
Output is correct |
5 |
Correct |
5 ms |
20312 KB |
Output is correct |
6 |
Correct |
4 ms |
20312 KB |
Output is correct |
7 |
Correct |
4 ms |
20312 KB |
Output is correct |
8 |
Incorrect |
4 ms |
20312 KB |
Wrong Answer[1] |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
20312 KB |
Output is correct |
2 |
Correct |
5 ms |
20312 KB |
Output is correct |
3 |
Correct |
5 ms |
20308 KB |
Output is correct |
4 |
Correct |
5 ms |
20564 KB |
Output is correct |
5 |
Correct |
5 ms |
20312 KB |
Output is correct |
6 |
Correct |
4 ms |
20312 KB |
Output is correct |
7 |
Correct |
4 ms |
20312 KB |
Output is correct |
8 |
Incorrect |
4 ms |
20312 KB |
Wrong Answer[1] |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
20312 KB |
Output is correct |
2 |
Correct |
5 ms |
20312 KB |
Output is correct |
3 |
Correct |
5 ms |
20308 KB |
Output is correct |
4 |
Correct |
5 ms |
20564 KB |
Output is correct |
5 |
Correct |
5 ms |
20312 KB |
Output is correct |
6 |
Correct |
4 ms |
20312 KB |
Output is correct |
7 |
Correct |
4 ms |
20312 KB |
Output is correct |
8 |
Incorrect |
4 ms |
20312 KB |
Wrong Answer[1] |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
20312 KB |
Output is correct |
2 |
Correct |
5 ms |
20312 KB |
Output is correct |
3 |
Correct |
5 ms |
20308 KB |
Output is correct |
4 |
Correct |
5 ms |
20564 KB |
Output is correct |
5 |
Correct |
5 ms |
20312 KB |
Output is correct |
6 |
Correct |
4 ms |
20312 KB |
Output is correct |
7 |
Correct |
4 ms |
20312 KB |
Output is correct |
8 |
Incorrect |
4 ms |
20312 KB |
Wrong Answer[1] |
9 |
Halted |
0 ms |
0 KB |
- |