#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
#define MAX 401010
#define MAXS 18
#define INF 1010101010
ll N, M;
vector<ll> X, Y, S, E, L, R;
ll prt1[MAX], prt2[MAX]; //tree
ll val1[MAX], val2[MAX]; //tree
ll ord1[MAX], ord2[MAX]; //tree
ll l1[MAX], l2[MAX]; //tree
ll r1[MAX], r2[MAX]; //tree
ll sp1[MAX][MAXS], sp2[MAX][MAXS];
pair<ll, ll> range1[MAX], range2[MAX];
vector<ll> adj[MAX];
struct dsu {
vector<ll> p;
dsu() {}
dsu(ll n) {
N = n;
p.clear();
p.resize(N);
ll i;
for (i = 0; i < N; i++) p[i] = i;
}
ll find(ll x) {
if (p[x] == x) return x;
return p[x] = find(p[x]);
}
void uni(ll u, ll v) {
u = find(u);
v = find(v);
if (u == v) return;
p.push_back(p.size());
p[v] = p[u] = p.size() - 1;
}
};
//merge_sort_segtree %$%#%#%$
struct segtree {
ll N, s;
vector<vector<ll>> tree;
vector<ll> l, r;
ll get(vector<ll>& v, ll l, ll r) {
return upper_bound(v.begin(), v.end(), r) - upper_bound(v.begin(), v.end(), l);
}
void init(ll x = 1) {
if (x >= s) {
if (!tree[x].empty()) sort(tree[x].begin(), tree[x].end());
l[x] = r[x] = x - s;
return;
}
init(x * 2);
init(x * 2 + 1);
l[x] = l[x * 2];
r[x] = r[x * 2 + 1];
tree[x] = tree[x * 2];
for (auto v : tree[x * 2 + 1]) tree[x].push_back(v);
sort(tree[x].begin(), tree[x].end());
}
segtree() {}
segtree(ll _N) {
N = _N;
s = 1 << (ll)ceil(log2(N));
tree.resize(2 * s + 1);
l.resize(2 * s + 1);
r.resize(2 * s + 1);
}
ll query(ll low, ll high, ll s, ll e, ll loc = 1) {
if (low == l[loc] && high == r[loc]) return get(tree[loc], s, e);
if (high <= r[loc * 2]) return query(low, high, s, e, loc * 2);
if (low >= l[loc * 2 + 1]) return query(low, high, s, e, loc * 2 + 1);
return query(low, r[loc * 2], s, e, loc * 2) | query(l[loc * 2 + 1], high, s, e, loc * 2 + 1);
}
};
void make_tree(ll mode = 0) {
ll i;
dsu d = dsu(N);
if (!mode) {
for (i = 0; i < 2 * N - 1; i++) l1[i] = r1[i] = -1;
for (i = 0; i < N; i++) {
for (auto v : adj[i]) {
if (v > i) continue;
if (d.find(v) == d.find(i)) continue;
ll ii, vv;
ii = d.find(i);
vv = d.find(v);
d.uni(ii, vv);
val1[d.p.size() - 1] = i;
l1[d.p.size() - 1] = ii;
r1[d.p.size() - 1] = vv;
prt1[ii] = prt1[vv] = d.p.size() - 1;
}
}
}
else {
for (i = 0; i < 2 * N - 1; i++) l2[i] = r2[i] = -1;
for (i = N - 1; i >= 0; i--) {
for (auto v : adj[i]) {
if (i > v) continue;
if (d.find(v) == d.find(i)) continue;
ll ii, vv;
ii = d.find(i);
vv = d.find(v);
d.uni(i, v);
val2[d.p.size() - 1] = i;
l2[d.p.size() - 1] = ii;
r2[d.p.size() - 1] = vv;
prt2[ii] = prt2[vv] = d.p.size() - 1;
}
}
}
}
ll cnt;
//rev_ord
void dfs1(ll x) {
if (x < N) {
ord1[x] = cnt++;
range1[x] = { ord1[x], ord1[x] };
return;
}
dfs1(l1[x]);
dfs1(r1[x]);
range1[x] = { range1[l1[x]].first, range1[r1[x]].second };
}
void dfs2(ll x) {
if (x < N) {
ord2[x] = cnt++;
range2[x] = { ord2[x], ord2[x] };
return;
}
dfs2(l2[x]);
dfs2(r2[x]);
range2[x] = { range2[l2[x]].first, range2[r2[x]].second };
}
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) {
tie(N, X, Y, S, E, L, R) = make_tuple(_N, _X, _Y, _S, _E, _L, _R);
vector<ll> ret;
ll i;
M = X.size();
for (i = 0; i < M; i++) adj[X[i]].push_back(Y[i]), adj[Y[i]].push_back(X[i]);
make_tree(0);
make_tree(1);
prt1[2 * N - 2] = prt2[2 * N - 2] = 2 * N - 2;
dfs1(2 * N - 2);
cnt = 0;
dfs2(2 * N - 2);
ll Q = S.size();
segtree mseg;
mseg = segtree(N);
for (i = 0; i <= 2 * N - 2; i++) sp1[i][0] = prt1[i];
for (i = 0; i <= 2 * N - 2; i++) sp2[i][0] = prt2[i];
for (ll k = 1; k < MAXS; k++) {
for (i = 0; i <= 2 * N - 2; i++) {
sp1[i][k] = sp1[sp1[i][k - 1]][k - 1];
sp2[i][k] = sp2[sp2[i][k - 1]][k - 1];
}
}
for (i = 0; i < N; i++) mseg.tree[mseg.s + ord1[i]].push_back(ord2[i]);
mseg.init();
for (i = 0; i < Q; i++) {
ll s, e, l, r;
s = S[i];
e = E[i];
l = L[i];
r = R[i];
ll v = e;
for (ll k = MAXS - 1; k >= 0; k--) if (val1[sp1[v][k]] <= r) v = sp1[v][k];
pair<ll, ll> wolf = range1[v];
v = s;
for (ll k = MAXS - 1; k >= 0; k--) if (val2[sp2[v][k]] >= l) v = sp2[v][k];
pair<ll, ll> human = range2[v];
if (mseg.query(wolf.first, wolf.second, human.first, human.second)) ret.push_back(1);
else ret.push_back(0);
}
return ret;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1002 ms |
148080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
