#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
using ll = long long;
using vi = vector<int>;
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
int M = (int)size(X), Q = (int)size(S);
vector<vector<int>> left(N), right(N);
for (int j = 0; j < M; ++j) {
int u = X[j], v = Y[j];
if (u > v) swap(u, v);
left[v].push_back(u);
right[u].push_back(v);
}
vector<int> pl(N), pr, p;
iota(begin(pl), end(pl), 0);
p = pr = pl;
auto find = [&](auto& self, int u, int lb, int ub) -> int {
return p[u] == u || p[u] < lb || ub < p[u] ? u : p[u] = self(self, p[u], lb, ub);
};
for (int u = 0; u < N; ++u) {
for (auto v : left[u]) {
v = find(find, v, 0, N - 1);
p[v] = pl[v] = u;
}
}
p = pr;
for (int u = N - 1; u >= 0; --u) {
for (auto v : right[u]) {
v = find(find, v, 0, N - 1);
p[v] = pr[v] = u;
}
}
vector<vector<int>> F(N);
for (int u = 0; u < N; ++u) {
int v = pr[u];
if (v != u) F[v].push_back(u);
}
vector<int> l(N), r(N);
int timer = 0;
auto tour = [&](auto& self, int u) -> void {
l[u] = timer;
for (auto v : F[u]) self(self, v);
r[u] = timer++;
};
for (int u = 0; u < N; ++u) {
if (pr[u] == u) tour(tour, u);
}
vector<int> subleft(Q), subright(Q), I(Q);
iota(begin(I), end(I), 0);
p = pl;
sort(begin(I), end(I), [&](int q1, int q2){ return R[q1] < R[q2]; });
for (auto q : I) subleft[q] = find(find, E[q], 0, R[q]);
p = pr;
sort(begin(I), end(I), [&](int q1, int q2){ return L[q1] > L[q2]; });
for (auto q : I) subright[q] = find(find, S[q], L[q], N - 1);
vector<vector<int>> queries(N);
for (auto q : I) {
int u = subleft[q], v = subright[q];
if (L[q] <= v && u <= R[q]) queries[u].push_back(q);
}
vector<set<int>> T(N);
vector<int> ans(Q);
for (int u = 0; u < N; ++u) {
T[u].insert(r[u]);
for (auto q : queries[u]) {
int v = subright[q];
auto iter = T[u].lower_bound(l[v]);
if (iter != end(T[u]) && *iter <= r[v]) {
ans[q] = 1;
break;
}
}
if (int v = pl[u]; v != u) {
if (size(T[v]) < size(T[u])) swap(T[v], T[u]);
T[v].merge(T[u]);
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
835 ms |
70700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
