#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
const int NAX = 4e5+10, LG = 20;
vector<int> edges[NAX], tree[2][NAX], arr[2], ids;
int in[2][NAX], out[2][NAX], p[2][NAX], L[2][NAX][LG];
int timer;
void add_edge(int x, int y, int which) {
tree[which][x].push_back(y);
tree[which][y].push_back(x);
}
int find_set(int x, int which) {
return x == p[which][x] ? x : p[which][x] = find_set(p[which][x], which);
}
void union_sets(int x, int y, int which) {
x = find_set(x, which);
y = find_set(y, which);
if(x == y) {
return;
}
p[which][y] = x;
add_edge(x, y, which);
}
void dfs(int x, int p, int which) {
in[which][x] = ++timer;
L[which][x][0] = p;
arr[which].push_back(x);
for(int i = 1; i < LG; ++i) {
int up = L[which][x][i - 1];
L[which][x][i] = ~up ? L[which][up][i - 1] : -1;
}
for(int to : tree[which][x]) {
if(to != p) {
dfs(to, x, which);
}
}
out[which][x] = timer;
}
int up(int x, int cutoff, int p) {
for(int i = LG - 1; i >= 0; --i) {
if(p == 0 && ~L[p][x][i] && L[p][x][i] >= cutoff) {
x = L[p][x][i];
}
if(p == 1 && ~L[p][x][i] && L[p][x][i] <= cutoff) {
x = L[p][x][i];
}
}
return x;
}
struct node {
vi v;
void merge(vi a, vi b) {
v.reserve((int)a.size() + (int)b.size());
for(int i = 0, j = 0; i < (int)a.size() || j < (int)b.size();) {
if(i < (int)a.size() && (j == (int)b.size() || a[i] < b[j])) {
v.push_back(a[i]);
++i;
} else {
v.push_back(b[j]);
++j;
}
}
}
int less(int x) {
int l = 0, r = (int)v.size() - 1, ans = -1;
while(r >= l) {
int m = l + r >> 1;
if(v[m] <= x) {
ans = m;
l = m + 1;
} else {
r = m - 1;
}
}
return ans+1;
}
} t[NAX];
void build(int l, int r, int p) {
if(l == r) {
t[p].v = {arr[1][l - 1]};
} else {
int m = l + r >> 1;
build(l, m, p << 1);
build(m+1, r, p << 1 | 1);
t[p].merge(t[p << 1].v, t[p << 1 | 1].v);
}
}
int query(int l, int r, int L, int R, int val, int p) {
if(l > R || L > r) {
return 0;
}
if(L <= l && R >= r) {
return t[p].less(val);
}
int m = l + r >> 1;
return query(l, m, L, R, val, p << 1) + query(m+1, r, L, R, val, p << 1 | 1);
}
vector<int> check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
for(int i = 0; i < X.size(); ++i) {
edges[X[i]].push_back(Y[i]);
edges[Y[i]].push_back(X[i]);
}
for(int i = 0; i < N; ++i) {
p[0][i] = p[1][i] = i;
}
for(int i = N - 1; i >= 0; --i) {
for(int to : edges[i]) {
if(to > i) {
union_sets(i, to, 0);
}
}
}
for(int i = 0; i < N; ++i) {
for(int to : edges[i]) {
if(to < i) {
union_sets(i, to, 1);
}
}
}
timer = -1; dfs(0, -1, 0);
timer = -1; dfs(N - 1, -1, 1);
ids = vector<int>(N);
for(int i = 0; i < N; ++i) {
ids[arr[0][i]] = i;
}
for(int i = 0; i < N; ++i) {
arr[1][i] = ids[arr[1][i]];
}
build(1, N, 1);
int Q = S.size();
vi A(Q);
for(int i = 0; i < Q; ++i) {
int s = up(S[i], L[i], 0);
int e = up(E[i], R[i], 1);
int cnt = query(1, N, in[0][e]+1, out[0][e]+1, out[0][s]+1, 1) - query(1, N, in[0][e]+1, out[0][e]+1, in[0][s], 1);
A[i] = cnt > 0;
}
return A;
}
Compilation message
werewolf.cpp: In member function 'int node::less(int)':
werewolf.cpp:68:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
68 | int m = l + r >> 1;
| ~~^~~
werewolf.cpp: In function 'void build(int, int, int)':
werewolf.cpp:83:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
83 | int m = l + r >> 1;
| ~~^~~
werewolf.cpp: In function 'int query(int, int, int, int, int, int)':
werewolf.cpp:96:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
96 | int m = 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:100:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for(int i = 0; i < X.size(); ++i) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
37996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
37996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
750 ms |
236388 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
37996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
