#include "werewolf.h"
#include <bits/stdc++.h>
struct Dsu {
std::vector <int> p;
Dsu(int size) {
p.resize(size);
std::iota(p.begin(), p.end(), 0);
}
inline int find(int v) {
return v == p[v] ? v : (p[v] = find(p[v]));
}
inline void unite(int u, int v) {
p[find(u)] = find(v);
}
};
struct Sparse {
std::vector <std::vector <int>> bin;
std::function <int (int, int)> cmp;
Sparse(const std::vector <int>& v, const std::function <int (int, int)>& _cmp) {
cmp = _cmp;
bin.resize(20, std::vector <int> (v.size()));
bin[0] = v;
for (int b = 1; b < 20; b++) {
for (int i = 0; i < (int) v.size(); i++) {
if (i + (1 << b) < (int) v.size()) {
bin[b][i] = cmp(bin[b - 1][i], bin[b - 1][i + (1 << (b - 1))]);
}
}
}
}
int query(int l, int r) {
if (l > r) {
std::swap(l, r);
}
int d = r - l + 1;
int b = 0;
while (d) {
b++;
d >>= 1;
}
b--;
return cmp(bin[b][l], bin[b][r - b]);
}
};
std::vector <int> check_validity(int n, std::vector <int> u, std::vector <int> v,
std::vector <int> s, std::vector <int> e, std::vector <int> l, std::vector <int> r) {
int m = u.size();
int q = s.size();
std::vector <std::vector <int>> g(n);
std::vector <int> deg(n, 0);
bool sub3 = n - 1 == m;
for (int i = 0; i < m; i++) {
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
sub3 &= ++deg[u[i]] <= 2;
sub3 &= ++deg[v[i]] <= 2;
}
if (sub3) {
std::vector <int> vals;
std::vector <int> ptrs(n);
std::queue <int> qq;
for (int i = 0; i < n; i++) {
if (deg[i] == 1) {
qq.push(i);
break;
}
}
std::vector <bool> vis(n, false);
while (qq.size()) {
int node = qq.front(); qq.pop();
if (vis[node]) {
continue;
}
vis[node] = true;
ptrs[node] = vals.size();
vals.push_back(node);
for (int x : g[node]) {
qq.push(x);
}
}
assert(vals.size() == ptrs.size());
Sparse sparse_mn(vals, [] (int x, int y) -> int { return std::min(x, y); });
Sparse sparse_mx(vals, [] (int x, int y) -> int { return std::max(x, y); });
std::vector <int> ans(q, 0);
for (int i = 0; i < q; i++) {
int le = std::min(ptrs[s[i]], ptrs[e[i]]);
int ri = le ^ ptrs[s[i]] ^ ptrs[e[i]];
int ll = le, rr = ri;
bool yes = false;
while (ll <= rr) {
int mid = (ll + rr) >> 1;
bool lok = sparse_mn.query(mid, ptrs[s[i]]) >= l[i];
bool rok = sparse_mx.query(mid, ptrs[e[i]]) <= r[i];
if (lok & rok) {
yes = true;
break;
}
if (!lok) {
if (le == ptrs[s[i]]) {
rr = mid - 1;
} else {
ll = mid + 1;
}
} else {
if (le == ptrs[s[i]]) {
ll = mid + 1;
} else {
rr = mid - 1;
}
}
}
ans[i] = yes;
}
return ans;
}
std::vector <int> ans(q, 0);
for (int i = 0; i < q; i++) {
Dsu dsu_l(n);
Dsu dsu_r(n);
for (int j = l[i]; j < n; j++) {
for (int x : g[j]) {
if (x >= l[i]) {
dsu_l.unite(j, x);
}
}
}
for (int j = 0; j <= r[i]; j++) {
for (int x : g[j]) {
if (x <= r[i]) {
dsu_r.unite(j, x);
}
}
}
for (int j = l[i]; j <= r[i]; j++) {
if (dsu_l.find(s[i]) == dsu_l.find(j) && dsu_r.find(e[i]) == dsu_r.find(j)) {
ans[i] = 1;
break;
}
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
651 ms |
55992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
