#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
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();
int Q = S.size();
vector<vector<int>> adj(N);
for (int i = 0; i < M; i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
if (N <= 3000 && M <= 6000 && Q <= 3000) {
vector<int> p(N);
function<int(int)> find = [&](int x) {
return x == p[x] ? x : p[x] = find(p[x]);
};
vector<vector<int>> s(N);
auto unite = [&](int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return;
}
if (s[x].size() > s[y].size()) {
swap(x, y);
}
for (int z : s[x]) {
p[z] = y;
s[y].push_back(z);
}
};
for (int i = 0; i < N; i++) {
p[i] = i;
s[i] = {i};
}
vector hi(N, vector<int>(N, -1));
for (int x = N - 1; x >= 0; x--) {
hi[x][x] = x;
for (int y : adj[x]) {
if (y < x || find(x) == find(y)) {
continue;
}
for (int u : s[find(x)]) {
for (int v : s[find(y)]) {
hi[u][v] = x;
hi[v][u] = x;
}
}
unite(x, y);
}
}
for (int i = 0; i < N; i++) {
p[i] = i;
s[i] = {i};
}
vector lo(N, vector<int>(N, -1));
for (int x = 0; x < N; x++) {
lo[x][x] = x;
for (int y : adj[x]) {
if (y > x || find(x) == find(y)) {
continue;
}
for (int u : s[find(x)]) {
for (int v : s[find(y)]) {
lo[u][v] = x;
lo[v][u] = x;
}
}
unite(x, y);
}
}
vector<int> ans(Q);
for (int i = 0; i < Q; i++) {
for (int j = L[i]; j <= R[i]; j++) {
if (hi[S[i]][j] >= L[i] && lo[j][E[i]] <= R[i]) {
ans[i] = 1;
}
}
}
return ans;
} else {
vector<int> A;
for (int i = 0; i < N; i++) {
if (adj[i].size() == 1) {
A.push_back(i);
A.push_back(adj[i][0]);
break;
}
}
while (A.size() < N) {
int x = A[A.size() - 2];
int y = A[A.size() - 1];
A.push_back(adj[y][0] ^ adj[y][1] ^ x);
}
// vector<int> lg(N + 1);
// for (int i = 2; i <= N; i++) {
// lg[i] = lg[i / 2] + 1;
// }
int lg = __lg(N);
vector smin(N, vector<int>(lg + 1));
vector smax(N, vector<int>(lg + 1));
for (int i = 0; i < N; i++) {
smin[i][0] = A[i];
smax[i][0] = A[i];
}
for (int j = 0; j < lg; j++) {
for (int i = 0; i + (2 << j) <= N; i++) {
smin[i][j + 1] = min(smin[i][j], smin[i + (1 << j)][j]);
smax[i][j + 1] = max(smax[i][j], smax[i + (1 << j)][j]);
}
}
auto qmin = [&](int l, int r) {
if (l == r) {
return N;
}
int k = __lg(r - l);
return min(smin[l][k], smin[r - (1 << k)][k]);
};
auto qmax = [&](int l, int r) {
if (l == r) {
return -1;
}
int k = __lg(r - l);
return max(smax[l][k], smax[r - (1 << k)][k]);
};
vector<int> B(N);
for (int i = 0; i < N; i++) {
B[A[i]] = i;
}
// for (int i = 0; i < N; i++) {
// cout << " " << A[i];
// }
// cout << "\n";
vector<int> ans(Q);
for (int i = 0; i < Q; i++) {
if (S[i] < L[i] || E[i] > R[i]) {
continue;
}
// cout << "---------\n";
int x = B[S[i]], u = -1;
int y = B[E[i]], v = -1;
if (x < y) {
int lo = x, hi = y;
while (lo < hi) {
int mi = (lo + hi + 1) / 2;
if (qmin(lo, mi + 1) >= L[i]) {
lo = mi;
} else {
hi = mi - 1;
}
}
u = lo;
lo = x, hi = y;
while (lo < hi) {
int mi = (lo + hi) / 2;
if (qmax(mi, y + 1) <= R[i]) {
hi = mi;
} else {
lo = mi + 1;
}
}
v = lo;
} else {
int lo = x, hi = y;
while (lo < hi) {
int mi = (lo + hi + 1) / 2;
if (qmax(lo, mi + 1) <= R[i]) {
lo = mi;
} else {
hi = mi - 1;
}
}
u = lo;
lo = x, hi = y;
while (lo < hi) {
int mi = (lo + hi) / 2;
if (qmin(mi, y + 1) >= L[i]) {
hi = mi;
} else {
lo = mi + 1;
}
}
v = lo;
}
assert(v != -1 && u != -1);
// cout << u << " " << v << "\n";
if (v <= u) {
ans[i] = 1;
}
}
return ans;
}
}
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:90:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
90 | while (A.size() < N) {
| ~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
189 ms |
71524 KB |
Output is correct |
| 11 |
Correct |
191 ms |
71456 KB |
Output is correct |
| 12 |
Correct |
158 ms |
71644 KB |
Output is correct |
| 13 |
Correct |
148 ms |
71500 KB |
Output is correct |
| 14 |
Correct |
144 ms |
71504 KB |
Output is correct |
| 15 |
Correct |
191 ms |
71612 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
483 ms |
63784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
189 ms |
71524 KB |
Output is correct |
| 11 |
Correct |
191 ms |
71456 KB |
Output is correct |
| 12 |
Correct |
158 ms |
71644 KB |
Output is correct |
| 13 |
Correct |
148 ms |
71500 KB |
Output is correct |
| 14 |
Correct |
144 ms |
71504 KB |
Output is correct |
| 15 |
Correct |
191 ms |
71612 KB |
Output is correct |
| 16 |
Incorrect |
483 ms |
63784 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
