#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int N = 200'000 + 10,
S = 500;
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 Q[N];
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 (n <= 3000 && m <= 6000 && q <= 3000) {
// vector<int> answer;
// for (int i = 0; i < q; ++i) {
// vector<vector<bool>> f(n, vector<bool>(2));
// vector<int> mk(n);
// for (int j = 0; j < n; ++j) mk[j] = (j < l[i] ? 0 : j <= r[i] ? 1 : 2);
// queue<int> que;
// f[s[i]][0] = f[s[i]][mk[s[i]] == 1] = true;
// que.push(s[i]);
// while (que.size()) {
// auto u = que.front(); que.pop();
// for (const auto& v : ad[u]) {
// if (f[v][0] || f[v][1]) continue;
// if (mk[v] >= 1) f[v][0] = f[u][0];
// if (mk[v] <= 1) f[v][1] = (f[u][1] || mk[v] == 1);
// if (f[v][0] || f[v][1]) que.push(v);
// }
// }
// answer.push_back(f[e[i]][1]);
// }
// return answer;
// }
if (line) {
int root;
for (int i = 0; i < n; ++i) if (ad[i].size() == 1) root = i;
dfs(root);
iota(Q, Q + q, 0);
sort(Q, Q + q, [&](const auto& a, const auto& b) {
return make_pair(l[a] / S, r[a]) < make_pair(l[b] / S, r[b]);
});
vector<int> answer(q);
set<int> w, b, h(a, a + n);
int lt = 0, rt = -1;
for (int i = 0; i < q; ++i) {
const auto& idx = Q[i];
while (rt < r[idx]) {
rt += 1;
if (h.count(rvs[rt])) h.erase(rvs[rt]);
b.insert(rvs[rt]);
}
while (rt > r[idx]) {
if (b.count(rvs[rt])) b.erase(rvs[rt]);
h.insert(rvs[rt]);
rt -= 1;
}
while (lt > l[idx]) {
lt -= 1;
if (w.count(rvs[lt])) w.erase(rvs[lt]);
b.insert(rvs[lt]);
}
while (lt < l[idx]) {
if (b.count(rvs[lt])) b.erase(rvs[lt]);
w.insert(rvs[lt]);
lt += 1;
}
if (b.size() == n || !h.size()) {
answer[idx] = 1;
continue;
}
if (rvs[s[idx]] < rvs[e[idx]]) {
auto vegan = h.upper_bound(rvs[e[idx]]);
if (vegan == h.begin()) {
answer[idx] = 1;
continue;
}
vegan = prev(vegan);
if (a[*vegan + 1] < l[idx]) continue;
auto meat = w.upper_bound(*vegan);
if (meat == w.begin() || a[*prev(meat)] > rvs[s[idx]]) answer[idx] = 1;
} else {
auto vegan = h.upper_bound(rvs[e[idx]]);
if (vegan == h.end()) {
answer[idx] = 1;
continue;
}
if (a[*vegan - 1] < l[idx]) continue;
auto meat = w.upper_bound(*vegan);
if (meat == w.end() || a[*meat] > rvs[e[idx]]) answer[idx] = 1;
}
}
return answer;
}
}
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:99:20: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
99 | if (b.size() == n || !h.size()) {
| ~~~~~~~~~^~~~
werewolf.cpp:133:1: warning: control reaches end of non-void function [-Wreturn-type]
133 | }
| ^
werewolf.cpp:59:8: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
59 | dfs(root);
| ~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
29784 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
29784 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4025 ms |
51028 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
29784 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
