#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int N = 200'000 + 10;
vector<int> ad[N];
int a[N], rvs[N], it;
void dfs(int u, int p = -1) {
a[it] = u; rvs[u] = it++;
for (const auto& v : ad[u]) if (v != p) dfs(v, u);
}
int f[N << 2][2];
void build(int s, int l, int r) {
if (l == r) {
f[s][0] = f[s][1] = a[l];
return;
}
int mid = l + r >> 1;
build(s << 1, l, mid); build(s << 1 | 1, mid + 1, r);
f[s][0] = min(f[s << 1][0], f[s << 1 | 1][0]);
f[s][1] = max(f[s << 1][1], f[s << 1 | 1][1]);
}
int getmi(int s, int l, int r, int u, int v) {
if (v < l || u > r) return 200'000;
if (u <= l && r <= v) return f[s][0];
int mid = l + r >> 1;
return min(getmi(s << 1, l, mid, u, v), getmi(s << 1 | 1, mid + 1, r, u, v));
}
int getma(int s, int l, int r, int u, int v) {
if (v < l || u > r) return -1;
if (u <= l && r <= v) return f[s][1];
int mid = l + r >> 1;
return max(getma(s << 1, l, mid, u, v), getma(s << 1 | 1, mid + 1, r, u, v));
}
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();
bool line = true;
for (int i = 0; i < m; ++i) {
int u = x[i], v = y[i];
ad[u].push_back(v);
ad[v].push_back(u);
line &= (ad[u].size() <= 2 && ad[v].size() <= 2);
}
if (line) {
int root;
for (int i = 0; i < n; ++i) if (ad[i].size() == 1) root = i;
dfs(root);
build(1, 0, n - 1);
vector<int> answer;
for (int i = 0; i < q; ++i) {
if (rvs[s[i]] < rvs[e[i]]) {
int st = rvs[s[i]], ed = rvs[e[i]];
int vegan = -1;
{
int lt = st, rt = ed;
while (lt <= rt) {
int mid = lt + rt >> 1;
if (getma(1, 0, n - 1, mid, ed) > r[i]) lt = (vegan = mid) + 1;
else rt = mid - 1;
}
}
int meat = -1;
{
int lt = st, rt = ed;
while (lt <= rt) {
int mid = lt + rt >> 1;
if (getmi(1, 0, n - 1, st, mid) < l[i]) rt = (meat = mid) - 1;
else lt = mid + 1;
}
}
if (meat == -1 || vegan == -1) {
answer.push_back(1);
continue;
}
if (meat <= vegan + 1) answer.push_back(0);
else answer.push_back(1);
} else {
int st = rvs[e[i]], ed = rvs[s[i]];
int vegan = -1;
{
int lt = st, rt = ed;
while (lt <= rt) {
int mid = lt + rt >> 1;
if (getma(1, 0, n - 1, st, mid) > r[i]) rt = (vegan = mid) - 1;
else lt = mid + 1;
}
}
int meat = -1;
{
int lt = st, rt = ed;
while (lt <= rt) {
int mid = lt + rt >> 1;
if (getmi(1, 0, n - 1, mid, ed) < l[i]) lt = (meat = mid) + 1;
else rt = mid - 1;;
}
}
if (meat == -1 || vegan == -1) {
answer.push_back(1);
continue;
}
if (meat >= vegan - 1) answer.push_back(0);
else answer.push_back(1);
}
}
return answer;
}
}
Compilation message
werewolf.cpp: In function 'void build(int, int, int)':
werewolf.cpp:21:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
21 | int mid = l + r >> 1;
| ~~^~~
werewolf.cpp: In function 'int getmi(int, int, int, int, int)':
werewolf.cpp:29:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
29 | int mid = l + r >> 1;
| ~~^~~
werewolf.cpp: In function 'int getma(int, int, int, int, int)':
werewolf.cpp:35:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
35 | int mid = l + r >> 1;
| ~~^~~
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:65:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | int mid = lt + rt >> 1;
| ~~~^~~~
werewolf.cpp:75:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
75 | int mid = lt + rt >> 1;
| ~~~^~~~
werewolf.cpp:95:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
95 | int mid = lt + rt >> 1;
| ~~~^~~~
werewolf.cpp:105:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
105 | int mid = lt + rt >> 1;
| ~~~^~~~
werewolf.cpp:123:1: warning: control reaches end of non-void function [-Wreturn-type]
123 | }
| ^
werewolf.cpp:54:8: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
54 | dfs(root);
| ~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
31328 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
31328 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1486 ms |
45824 KB |
Output is correct |
| 2 |
Correct |
1679 ms |
45556 KB |
Output is correct |
| 3 |
Correct |
1698 ms |
45524 KB |
Output is correct |
| 4 |
Correct |
1678 ms |
45588 KB |
Output is correct |
| 5 |
Correct |
1652 ms |
45376 KB |
Output is correct |
| 6 |
Correct |
1542 ms |
45612 KB |
Output is correct |
| 7 |
Correct |
1720 ms |
45404 KB |
Output is correct |
| 8 |
Correct |
1743 ms |
45556 KB |
Output is correct |
| 9 |
Correct |
714 ms |
45612 KB |
Output is correct |
| 10 |
Correct |
931 ms |
45460 KB |
Output is correct |
| 11 |
Correct |
1022 ms |
45512 KB |
Output is correct |
| 12 |
Correct |
1337 ms |
45576 KB |
Output is correct |
| 13 |
Correct |
1749 ms |
45620 KB |
Output is correct |
| 14 |
Correct |
1720 ms |
45508 KB |
Output is correct |
| 15 |
Correct |
1703 ms |
45652 KB |
Output is correct |
| 16 |
Correct |
1654 ms |
45548 KB |
Output is correct |
| 17 |
Correct |
1718 ms |
45644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
31328 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
