#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
using VI = vector<int>;
const int maxn = 4e5 + 5;
int N, M, Q;
int U[maxn], V[maxn];
namespace pre {
int parent[maxn];
vector<int> g[maxn], w[maxn];
int sz[maxn], par[maxn], pw[maxn];
int in[maxn], tour[maxn];
int tym = 0;
void init() {
for(int i = 0; i < N; i++) {
sz[i] = 1, par[i] = i;
}
}
int find(int u) {
return par[u] == u ? u : find(par[u]);
}
void join(int u, int v) {
int weight = max(u, v);
u = find(u), v = find(v);
if(u == v) return;
if(sz[u] > sz[v]) swap(u, v);
par[u] = v, pw[u] = weight;
sz[v] += sz[u];
g[v].emplace_back(u);
w[v].emplace_back(weight);
}
void dfs(int u) {
tour[tym] = u;
in[u] = tym++;
for(int v : g[u]) {
dfs(v);
}
}
pair<int, int> range(int u, int weight) {
while(par[u] != u and pw[u] <= weight)
u = par[u];
if(sz[u] == 1) // leaf
return {in[u], in[u]};
int it = upper_bound(all(w[u]), weight) - w[u].begin();
if(it == 0) // can't go nowhere
return {in[u], in[u]};
int v = g[u][it - 1];
return {in[u], in[v] + sz[v] - 1};
}
}
namespace suf {
int parent[maxn];
vector<int> g[maxn], w[maxn];
int sz[maxn], par[maxn], pw[maxn];
int in[maxn], tour[maxn];
int tym = 0;
void init() {
for(int i = 0; i < N; i++) {
sz[i] = 1, par[i] = i;
}
}
int find(int u) {
return par[u] == u ? u : find(par[u]);
}
void join(int u, int v) {
int weight = min(u, v);
u = find(u), v = find(v);
if(u == v) return;
if(sz[u] > sz[v]) swap(u, v);
par[u] = v, pw[u] = weight;
sz[v] += sz[u];
g[v].emplace_back(u);
w[v].emplace_back(weight);
}
void dfs(int u) {
tour[tym] = u;
in[u] = tym++;
for(int v : g[u]) {
dfs(v);
}
}
pair<int, int> range(int u, int weight) {
while(par[u] != u and pw[u] >= weight)
u = par[u];
if(sz[u] == 1) // leaf
return {in[u], in[u]};
int it = upper_bound(all(w[u]), weight, [](int x, int y){ return x > y; }) - w[u].begin();
if(it == 0) // can't go nowhere
return {in[u], in[u]};
int v = g[u][it - 1];
return {in[u], in[v] + sz[v] - 1};
}
}
vector<int> check_validity(int _N, VI X, VI Y, VI S, VI E, VI L, VI R) {
N = _N, M = X.size(), Q = S.size();
for(int i = 0; i < M; i++) {
U[i] = X[i], V[i] = Y[i];
if(U[i] > V[i]) swap(U[i], V[i]);
}
pre::init();
suf::init();
vector<int> p(M), q(M);
iota(p.begin(), p.end(), 0);
iota(q.begin(), q.end(), 0);
sort(p.begin(), p.end(), [](int x, int y){ return V[x] < V[y]; });
sort(q.begin(), q.end(), [](int x, int y){ return U[x] > U[y]; });
for(int i : p)
pre::join(U[i], V[i]);
for(int i : q)
suf::join(U[i], V[i]);
pre::dfs(pre::find(0));
suf::dfs(suf::find(0));
int tour[maxn], index[maxn];
for(int i = 0; i < N; i++) {
index[pre::tour[i]] = i;
}
for(int i = 0; i < N; i++) {
tour[i] = index[suf::tour[i]];
}
vector<int> ans(Q);
struct data {
int L, id, op, l, r;
data() {}
data(int _L, int _id, int _op, int _l, int _r) {
L = _L, id = _id, op = _op, l = _l, r = _r;
}
bool operator < (const data &that) const {
return L < that.L;
}
};
vector<data> shit_load;
for(int i = 0; i < Q; i++) {
int l1, l2, r1, r2;
tie(l1, r1) = pre::range(E[i], R[i]);
tie(l2, r2) = suf::range(S[i], L[i]);
shit_load.push_back(data(r2, i, +1, l1, r1));
if(l2 != 0) shit_load.push_back(data(l2 - 1, i, -1, l1, r1));
}
int ft[maxn];
memset(ft, 0, sizeof ft);
auto update = [&](int i) {
i++;
for(; i < maxn; i += i & -i) ft[i]++;
};
auto query = [&](int l, int r) {
r++;
int ret = 0;
for(; l > 0; l -= l & -l) ret -= ft[l];
for(; r > 0; r -= r & -r) ret += ft[r];
return ret;
};
sort(all(shit_load));
int it = 0;
for(data e : shit_load) {
while(it < N and it <= e.L) {
update(tour[it]);
it++;
}
ans[e.id] += e.op * query(e.l, e.r);
}
for(int &i : ans) i = bool(i);
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
39544 KB |
Output is correct |
2 |
Correct |
34 ms |
39672 KB |
Output is correct |
3 |
Correct |
36 ms |
39544 KB |
Output is correct |
4 |
Correct |
34 ms |
39552 KB |
Output is correct |
5 |
Correct |
33 ms |
39544 KB |
Output is correct |
6 |
Correct |
34 ms |
39544 KB |
Output is correct |
7 |
Correct |
34 ms |
39552 KB |
Output is correct |
8 |
Correct |
34 ms |
39524 KB |
Output is correct |
9 |
Correct |
35 ms |
39672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
39544 KB |
Output is correct |
2 |
Correct |
34 ms |
39672 KB |
Output is correct |
3 |
Correct |
36 ms |
39544 KB |
Output is correct |
4 |
Correct |
34 ms |
39552 KB |
Output is correct |
5 |
Correct |
33 ms |
39544 KB |
Output is correct |
6 |
Correct |
34 ms |
39544 KB |
Output is correct |
7 |
Correct |
34 ms |
39552 KB |
Output is correct |
8 |
Correct |
34 ms |
39524 KB |
Output is correct |
9 |
Correct |
35 ms |
39672 KB |
Output is correct |
10 |
Correct |
41 ms |
40328 KB |
Output is correct |
11 |
Correct |
41 ms |
40284 KB |
Output is correct |
12 |
Correct |
42 ms |
40284 KB |
Output is correct |
13 |
Correct |
41 ms |
40296 KB |
Output is correct |
14 |
Correct |
42 ms |
40280 KB |
Output is correct |
15 |
Correct |
40 ms |
40312 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
593 ms |
79864 KB |
Output is correct |
2 |
Correct |
445 ms |
82920 KB |
Output is correct |
3 |
Correct |
456 ms |
83060 KB |
Output is correct |
4 |
Correct |
522 ms |
87876 KB |
Output is correct |
5 |
Correct |
527 ms |
87944 KB |
Output is correct |
6 |
Correct |
564 ms |
87932 KB |
Output is correct |
7 |
Correct |
614 ms |
88032 KB |
Output is correct |
8 |
Correct |
437 ms |
82992 KB |
Output is correct |
9 |
Correct |
402 ms |
84260 KB |
Output is correct |
10 |
Correct |
414 ms |
83556 KB |
Output is correct |
11 |
Correct |
432 ms |
83792 KB |
Output is correct |
12 |
Correct |
454 ms |
87908 KB |
Output is correct |
13 |
Correct |
446 ms |
83164 KB |
Output is correct |
14 |
Correct |
446 ms |
82992 KB |
Output is correct |
15 |
Correct |
445 ms |
83040 KB |
Output is correct |
16 |
Correct |
442 ms |
83484 KB |
Output is correct |
17 |
Correct |
574 ms |
88068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
39544 KB |
Output is correct |
2 |
Correct |
34 ms |
39672 KB |
Output is correct |
3 |
Correct |
36 ms |
39544 KB |
Output is correct |
4 |
Correct |
34 ms |
39552 KB |
Output is correct |
5 |
Correct |
33 ms |
39544 KB |
Output is correct |
6 |
Correct |
34 ms |
39544 KB |
Output is correct |
7 |
Correct |
34 ms |
39552 KB |
Output is correct |
8 |
Correct |
34 ms |
39524 KB |
Output is correct |
9 |
Correct |
35 ms |
39672 KB |
Output is correct |
10 |
Correct |
41 ms |
40328 KB |
Output is correct |
11 |
Correct |
41 ms |
40284 KB |
Output is correct |
12 |
Correct |
42 ms |
40284 KB |
Output is correct |
13 |
Correct |
41 ms |
40296 KB |
Output is correct |
14 |
Correct |
42 ms |
40280 KB |
Output is correct |
15 |
Correct |
40 ms |
40312 KB |
Output is correct |
16 |
Correct |
593 ms |
79864 KB |
Output is correct |
17 |
Correct |
445 ms |
82920 KB |
Output is correct |
18 |
Correct |
456 ms |
83060 KB |
Output is correct |
19 |
Correct |
522 ms |
87876 KB |
Output is correct |
20 |
Correct |
527 ms |
87944 KB |
Output is correct |
21 |
Correct |
564 ms |
87932 KB |
Output is correct |
22 |
Correct |
614 ms |
88032 KB |
Output is correct |
23 |
Correct |
437 ms |
82992 KB |
Output is correct |
24 |
Correct |
402 ms |
84260 KB |
Output is correct |
25 |
Correct |
414 ms |
83556 KB |
Output is correct |
26 |
Correct |
432 ms |
83792 KB |
Output is correct |
27 |
Correct |
454 ms |
87908 KB |
Output is correct |
28 |
Correct |
446 ms |
83164 KB |
Output is correct |
29 |
Correct |
446 ms |
82992 KB |
Output is correct |
30 |
Correct |
445 ms |
83040 KB |
Output is correct |
31 |
Correct |
442 ms |
83484 KB |
Output is correct |
32 |
Correct |
574 ms |
88068 KB |
Output is correct |
33 |
Correct |
626 ms |
87768 KB |
Output is correct |
34 |
Correct |
402 ms |
74860 KB |
Output is correct |
35 |
Correct |
566 ms |
88212 KB |
Output is correct |
36 |
Correct |
621 ms |
88052 KB |
Output is correct |
37 |
Correct |
558 ms |
88108 KB |
Output is correct |
38 |
Correct |
587 ms |
88220 KB |
Output is correct |
39 |
Correct |
562 ms |
86240 KB |
Output is correct |
40 |
Correct |
589 ms |
95136 KB |
Output is correct |
41 |
Correct |
493 ms |
87488 KB |
Output is correct |
42 |
Correct |
496 ms |
83488 KB |
Output is correct |
43 |
Correct |
553 ms |
86544 KB |
Output is correct |
44 |
Correct |
519 ms |
87952 KB |
Output is correct |
45 |
Correct |
495 ms |
86860 KB |
Output is correct |
46 |
Correct |
497 ms |
81996 KB |
Output is correct |
47 |
Correct |
464 ms |
83592 KB |
Output is correct |
48 |
Correct |
459 ms |
83148 KB |
Output is correct |
49 |
Correct |
473 ms |
83720 KB |
Output is correct |
50 |
Correct |
453 ms |
83116 KB |
Output is correct |
51 |
Correct |
586 ms |
95168 KB |
Output is correct |
52 |
Correct |
583 ms |
95228 KB |
Output is correct |