#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int maxn_12 = 3e3 + 2;
const int maxn_3 = 2e5 + 2;
const int lg = 19;
vector <int> ad [maxn_3];
bitset <maxn_12> vis1, vis2;
int act[maxn_3];
int sp[2][maxn_3][lg]; // sp[0] -> min r, sp[1] -> max l
int lg2(int x) {
int ct = 0;
int k = 1;
while (k <= x) {
k *= 2; ct++;
}
return ct-1;
}
void dfs1 (int u, int l, int r) {
vis1[u] = 1;
for (int v: ad[u]) {
if (v < l || vis1[v]) continue;
dfs1(v, l, r);
}
}
int dfs2 (int u, int l, int r) {
vis2[u] = 1;
bool b = (vis1[u]);
for (int v: ad[u]) {
if (v > r || vis2[v]) continue;
b|=dfs2(v, l, r);
}
return b;
}
void label (int u, int p, int nr) {
act[u] = nr;
for (int v: ad[u]) {
if (v == p) continue;
label(v, u, nr + 1);
}
}
int query0 (int l, int r) {
int k = lg2(r - l + 1);
return min(sp[0][l][k], sp[0][r - (1 << k) + 1][k]);
}
int query1 (int l, int r) {
int k = lg2(r - l + 1);
return max(sp[1][l][k], sp[1][r - (1 << k) + 1][k]);
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
for (int i = 0; i < X.size(); i++){
ad[X[i]].push_back(Y[i]);
ad[Y[i]].push_back(X[i]);
}
int Q = S.size();
vector<int> A(Q);
if (0){
// if (N <= 3000 && Q <= 3000 && X.size() <= 6000){
for (int i = 0; i < Q; ++i) {
vis1 = vis2 = 0;
dfs1(S[i], L[i], R[i]);
A[i] = dfs2(E[i], L[i], R[i]);
}
}
else {
for (int i = 0; i < N; i++){
if (ad[i].size() == 1) {
label(i, -1, 0);
break;
}
for (int i = 0; i < N; i++){
sp[0][i][0] = R[act[i]];
sp[1][i][0] = L[act[i]];
}
for (int k = 1; k < lg; k++){
for (int i = 0; i + (1 << k) - 1 < N; i++){
sp[0][i][k] = min(sp[0][i][k-1], sp[0][i + (1 << (k - 1))][k-1]);
sp[1][i][k] = max(sp[1][i][k-1], sp[1][i + (1 << (k - 1))][k-1]);
}
}
}
for (int i = 0; i < Q; ++i) {
int n1 = act[S[i]], n2 = act[R[i]];
if (n1 < n2){
int l = n1, r = n2, f1 = -1, f2 = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (query0(n1, mid) >= S[i]) {
f1 = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
l = n1, r = n2, f2 = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (query1(mid, n2) <= R[i]) {
f2 = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
}
A[i] = (f1 >= f2);
}
else {
// swap(n1, n2);
int l = n1, r = n2, f1 = -1, f2 = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (query1(n1, mid) <= R[i]) {
f1 = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
while (l <= r) {
int mid = (l + r) / 2;
if (query0(mid, n2) >= S[i]) {
f2 = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
}
l = n1, r = n2, f2 = -1;
A[i] = (f1 >= f2);
}
}
}
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:60:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for (int i = 0; i < X.size(); i++){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
347 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
347 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4065 ms |
51196 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
347 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
