#include "werewolf.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pp pop_back
#define mp make_pair
#define bb back
#define ff first
#define ss second
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 Q = s.size();
vector<int> A(Q, 0);
vector<int> path[n];
for (int i = 0; i < x.size(); i++) {
path[x[i]].pb(y[i]);
path[y[i]].pb(x[i]);
}
int level[n];
int jump[n][20][3];
memset(jump, -1, sizeof(jump));
queue<pair<int, int> > bfs;
bfs.push({0, 0});
while (!bfs.empty()) {
int now = bfs.front().ff;
level[now] = bfs.front().ss;
bfs.pop();
for (int next : path[now]) {
if (next == jump[now][0][1]) continue;
jump[next][0][0] = min(now, next);
jump[next][0][1] = now;
jump[next][0][2] = max(now, next);
bfs.push({next, level[now]+1});
}
}
for (int j = 1; j < 20; j++) {
for (int i = 0; i < n; i++) {
if (jump[i][j-1][1] == -1) continue;
jump[i][j][1] = jump[jump[i][j-1][1]][j-1][1];
jump[i][j][0] = min(jump[i][j-1][0], jump[jump[i][j-1][1]][j-1][0]);
jump[i][j][2] = max(jump[i][j-1][2], jump[jump[i][j-1][1]][j-1][2]);
}
}
for (int q = 0; q < Q; q++) {
if (s[q] < l[q] || e[q] > r[q]) continue;
int a = s[q], b = e[q], c;
if (level[a] > level[b])
swap(a, b);
for (int i = 19; i >= 0; i--) {
if (level[b] - (1<<i) >= level[a])
b = jump[b][i][1];
}
for (int i = 19; i >= 0; i--) {
if (jump[b][i][1] != jump[a][i][1])
b = jump[b][i][1], a = jump[a][i][1];
}
int mx = -1, mn = n+1, ta, tb;
if (a != b)
a = jump[a][0][1], b = jump[b][0][1];
c = a;
a = s[q], b = e[q];
// cout << c << '\n';
for (int i = 19; i >= 0; i--) {
if (jump[a][i][0] < l[q] || level[a]-(1<<i) < level[c]) continue;
a = jump[a][i][1];
}
// cout << "WUT\n";
// cout << a << ' ';
ta = a;
if (a != c) {
a = jump[a][0][1];
if (a > r[q]) mx = n+1;
}
for (int i = 19; i >= 0; i--) {
if (level[a] - (1<<i) < level[c]) continue;
mx = max(mx, jump[a][i][2]);
a = jump[a][i][1];
}
for (int i = 19; i >= 0; i--) {
if (jump[b][i][2] > r[q] || level[b]-(1<<i) < level[c]) continue;
b = jump[b][i][1];
}
// cout << b << '\n';
tb = b;
if (b != c) {
b = jump[b][0][1];
if (b < l[q]) mn = -1;
}
for (int i = 19; i >= 0; i--) {
if (level[b] - (1<<i) < level[c]) continue;
mn = min(mn, jump[b][i][0]);
b = jump[b][i][1];
}
// cout << ta << ' ' << tb << ' ' << mn << ' ' << mx << '\n';
if (ta != c && tb != c) continue;
if ((ta < l[q] || ta > r[q]) && (tb < l[q] || tb > r[q])) continue;
if (ta >= l[q] && ta <= r[q] && mx <= r[q]) A[q] = 1;
if (tb >= l[q] && tb <= r[q] && mn >= l[q]) A[q] = 1;
// if (mn >= l[q] && mx <= r[q]) A[q] = 1;
// if (mn < l[q] || mx > r[q]) continue;
// A[q] = 1;
}
return A;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/
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:19:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | for (int i = 0; i < x.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1387 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1387 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
982 ms |
69632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1387 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
