#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define f first
#define s second
const int N = 4e5, inf = 1e9;
vector<int> V[2][N];
int cur[2], x[2][N], p[2][N][20], timer[2], tmin[2][N], tmout[2][N], pos[2][N], n;
int par[2][N];
vector<pii> edges;
set<int> s[4 * N];
int find(int u,int t) {
return (par[t][u] == u ? u : par[t][u] = find(par[t][u], t));
}
void build(vector<pair<int,int> > edges, int t) {
cur[t] = n;
for(int i = 1; i <= cur[t]; i++) par[t][i] = i;
for(int i = 0; i < edges.size(); i++) {
int u = edges[i].f, v = edges[i].s;
if(find(u, t) != find(v, t)) {
++cur[t]; par[t][cur[t]] = cur[t];
V[t][cur[t]].push_back(find(u, t));
V[t][cur[t]].push_back(find(v, t));
p[t][find(u, t)][0] = par[t][find(u, t)] = cur[t];
p[t][find(v, t)][0] = par[t][find(v, t)] = cur[t];
x[t][cur[t]] = u;
}
}
cur[t]++; if(!t)x[t][cur[t]] = inf;
for(int i = 1; i < cur[t]; i++) {
if(find(i, t) == i) p[t][i][0] = cur[t], V[t][cur[t]].push_back(i);
}
for(int j = 1; j <= 18; j++) {
for(int i = 1; i <= cur[t]; i++) {
p[t][i][j] = p[t][p[t][i][j - 1]][j - 1];
}
}
}
void dfs(int u, int t) {
tmin[t][u] = ++timer[t];
pos[t][timer[t]] = u;
for(int i = 0; i < V[t][u].size(); i++) {
dfs(V[t][u][i], t);
}
tmout[t][u] = timer[t];
}
int get(int u,int t, int X) {
for(int i = 18; i >= 0; i--) {
if(!p[t][u][i]) continue;
if(t && x[t][p[t][u][i]] >= X) u = p[t][u][i];
else if(!t && x[t][p[t][u][i]] <= X) u = p[t][u][i];
}
return u;
}
void build(int u,int l,int r) {
for(int i = l; i <= r; i++) if(pos[1][i] <= n)s[u].insert(tmin[0][pos[1][i]]);
if(l == r) return;
int mid = (l + r) / 2;
build(2 * u, l, mid); build(2 * u + 1, mid + 1, r);
}
bool get(int u, int st,int en,int l,int r,int x,int y) {
if(l > en || r < st) return 0;
if(st <= l && r <= en) {
if(s[u].upper_bound(x - 1) != s[u].end()) {
if(*s[u].upper_bound(x - 1) <= y) return 1;
}
return 0;
}
int mid = (l + r) / 2;
return get(2 * u, st, en, l, mid, x, y)|get(2 * u + 1, st, en, mid + 1, r, x, y);
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
vector<pair<int,int> > edges; n = N;
for(int i = 0; i < X.size(); i++) {
++X[i]; ++Y[i];
edges.push_back({max(X[i], Y[i]), min(X[i], Y[i])});
}
sort(edges.begin(), edges.end());
build(edges, 0); // werewolf
for(int i = 0; i < edges.size(); i++) {
swap(edges[i].f, edges[i].s);
}
sort(edges.rbegin(), edges.rend());
build(edges, 1); // human
dfs(cur[0], 0);
dfs(cur[1], 1);
build(1, 1, cur[1]);
vector<int> ans(S.size());
for(int i = 0; i < S.size(); i++) {
int l = L[i], r = R[i], u = S[i], v = E[i];
++l, ++r, ++u, ++v;
if(u < l || v > r) {
ans[i] = 0;
continue;
}
u = get(u, 1, l);
v = get(v, 0, r);
ans[i] = get(1, tmin[1][u], tmout[1][u], 1, cur[1], tmin[0][v], tmout[0][v]);
}
return ans;
}
Compilation message
werewolf.cpp: In function 'void build(std::vector<std::pair<int, int> >, int)':
werewolf.cpp:18:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | for(int i = 0; i < edges.size(); i++) {
| ~~^~~~~~~~~~~~~~
werewolf.cpp: In function 'void dfs(int, int)':
werewolf.cpp:42:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(int i = 0; i < V[t][u].size(); i++) {
| ~~^~~~~~~~~~~~~~~~
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:77:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int i = 0; i < X.size(); i++) {
| ~~^~~~~~~~~~
werewolf.cpp:85:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(int i = 0; i < edges.size(); i++) {
| ~~^~~~~~~~~~~~~~
werewolf.cpp:98:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for(int i = 0; i < S.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
94364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
94364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1361 ms |
380360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
94364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
