#include "werewolf.h"
#include <queue>
#include <iostream>
using namespace std;
const int MAX_N = 2e5+1, LG = 19;
int mx[LG][MAX_N], mn[LG][MAX_N];
int getMN(int l, int r) {
int i = 0, p2 = 1;
while (p2 <= r-l+1) ++i, p2 <<= 1;
--i, p2 >>= 1;
return min(mn[i][l], mn[i][r-p2+1]);
}
int getMX(int l, int r) {
int i = 0, p2 = 1;
while (p2 <= r-l+1) ++i, p2 <<= 1;
--i, p2 >>= 1;
return max(mx[i][l], mx[i][r-p2+1]);
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
int M = X.size(), Q = S.size();
vector<int> A(Q);
// if (N <= 3000 && M <= 6000 && Q <= 3000) { // subtasks 1 and 2
// vector<vector<int>> g(N);
// for (int i = 0; i < M; ++i) {
// g[X[i]].push_back(Y[i]);
// g[Y[i]].push_back(X[i]);
// }
// for (int qq = 0; qq < Q; ++qq) {
// int s = S[qq], e = E[qq], l = L[qq], r = R[qq];
// // bfs from start as human
// vector<bool> canHuman(N);
// queue<int> q;
// q.push(s), canHuman[s] = true;
// while (!q.empty()) {
// int x = q.front();
// q.pop();
// for (int y : g[x]) {
// if (!canHuman[y] && y >= l) q.push(y), canHuman[y] = true;
// }
// }
// vector<bool> canWolf(N);
// q.push(e), canWolf[e] = true;
// while (!q.empty()) {
// int x = q.front();
// q.pop();
// for (int y : g[x]) {
// if (!canWolf[y] && y <= r) q.push(y), canWolf[y] = true;
// }
// }
// for (int i = 0; i < N; ++i) {
// if (canHuman[i] && canWolf[i] && l <= i && i <= r) A[qq] = 1;
// }
// }
// } else { // subtask 3
// find order for nodes
vector<vector<int>> g(N);
for (int i = 0; i < M; ++i) {
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
int endPoint = 0;
for (int i = 0; i < N; ++i) {
if (g[i].size() == 1) {
endPoint = i;
break;
}
}
// move from endpoint and mark nodes
vector<int> id(N);
id[0] = endPoint;
for (int i = 1, cur = g[id[0]][0]; i < N; ++i) {
id[i] = cur;
cur = g[cur][0] + g[cur][1] - id[i-1];
}
for (int i : id) cerr << i << ' '; cerr << endl;
vector<int> linePos(N);
for (int i = 0; i < N; ++i) linePos[id[i]] = i;
// store range maximums and minimums with sparse table
for (int i = 0; i < N; ++i) mx[0][i] = mn[0][i] = id[i];
for (int i = 1, p2 = 1; i < LG; ++i, p2<<=1) {
for (int j = 0; j < N; ++j) {
mx[i][j] = max(mx[i-1][j], mx[i-1][j+p2]);
mn[i][j] = min(mn[i-1][j], mn[i-1][j+p2]);
}
}
for (int qq = 0; qq < Q; ++qq) {
int s = S[qq], e = E[qq], l = L[qq], r = R[qq];
s = linePos[s], e = linePos[e];
if (s < e) {
// find last H (only allowing humans) after start
// (last one > R)
int left = s-1, right = e; // there is an H on or after left, not right
while (left+1 < right) {
int mid = (left + right) / 2;
if (getMX(mid, e) > r) left = mid;
else right = mid;
}
int lastH = left;
// find first W (only allowing werewolves) after start
// (first one < L)
left = s, right = e+1; // there is W on or before right, not left
while (left+1 < right) {
int mid = (left + right) / 2;
if (getMN(s, mid) < l) right = mid;
else left = mid;
}
int firstW = right;
if (lastH+1 < firstW) A[qq] = 1;
} else {
// find last W (only allowing werewolves) after end
// (last one < L)
int left = e-1, right = s; // there is a W on or after left, not right
while (left+1 < right) {
int mid = (left + right) / 2;
if (getMX(mid, s) < l) left = mid;
else right = mid;
}
int lastW = left;
// find first H (only allowing humans) after end
// (first one > R)
left = e, right = s+1; // there is an H on or before right, not left
while (left+1 < right) {
int mid = (left + right) / 2;
if (getMN(e, mid) < l) right = mid;
else left = mid;
}
int firstH = right;
if (lastW+1 < firstH) A[qq] = 1;
}
}
// }
return A;
}
Compilation message
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:86:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
86 | for (int i : id) cerr << i << ' '; cerr << endl;
| ^~~
werewolf.cpp:86:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
86 | for (int i : id) cerr << i << ' '; cerr << endl;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
987 ms |
60332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
