#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int N = 1 << 18;
int n, m, q, par[N];
vector<int> g[N];
vector<int> t1[N], t2[N];
vector<int> sl[N], sr[N];
int al[N], ar[N];
int find(int u) { return par[u] = par[u] == u ? u : find(par[u]); }
int in[N], out[N], pos[N];
void dfs(int u) {
static int idx = 0;
pos[in[u] = ++idx] = u;
for(int v : t1[u])
dfs(v);
out[u] = idx;
}
int sz[N], in1[N], out1[N], pos1[N];
void pre(int u) {
static int id = 0;
sz[pos1[in1[u] = ++id] = u]++;
for(int &v : t2[u]) {
pre(v), sz[u] += sz[v];
if(sz[v] > sz[t2[u][0]]) swap(v, t2[u][0]);
}
out1[u] = id;
}
bool t[N<<1];
void update(int x, bool v) {
for(t[x += N] = v; x != 1; x >>= 1) t[x>>1] = t[x] | t[x^1];
}
bool query(int l, int r) {
bool ret = false;
for(l += N, r += N+1; l < r; l >>= 1, r >>= 1) {
if(l & 1) ret |= t[l++];
if(r & 1) ret |= t[--r];
}
return ret;
}
vector<int> ans;
vector<int> zz[N];
void solve(int u, bool keep) {
for(int v : t2[u]) if(v != t2[u][0]) solve(v, false);
if(t2[u].size()) solve(t2[u][0], true);
update(in[u], true);
for(int v : t2[u]) if(v != t2[u][0])
for(int i = in1[v]; i <= out1[v]; ++i) update(in[pos1[i]], true);
for(int x : zz[u]) ans[x] = query(in[al[x]], out[al[x]]);
if(!keep) for(int i = in1[u]; i <= out1[u]; ++i) update(in[pos1[i]], false);
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
n = N, m = X.size(), q = S.size();
ans.resize(q);
for(int i = 0; i < m; ++i) g[X[i]].emplace_back(Y[i]), g[Y[i]].emplace_back(X[i]);
for(int i = 0; i < q; ++i) sl[L[i]].emplace_back(i);
for(int i = 0; i < q; ++i) sr[R[i]].emplace_back(i);
for(int i = n-1; ~i; --i) {
par[i] = i;
for(int v : g[i]) if(v > i) {
int a = find(i), b = find(v);
if(a != b) {
t1[a].emplace_back(b);
par[b] = a;
}
}
for(int v : sl[i]) {
al[v] = find(S[v]);
}
}
for(int i = 0; i < n; ++i) {
par[i] = i;
for(int v : g[i]) if(v < i) {
int a = find(i), b = find(v);
if(a != b) {
t2[a].emplace_back(b);
par[b] = a;
}
}
for(int v : sr[i]) {
zz[find(E[v])].emplace_back(v);
}
}
dfs(0);
pre(n-1);
solve(n-1, true);
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
34 ms |
37376 KB |
Output is correct |
2 |
Correct |
34 ms |
37340 KB |
Output is correct |
3 |
Correct |
33 ms |
37372 KB |
Output is correct |
4 |
Correct |
33 ms |
37340 KB |
Output is correct |
5 |
Correct |
33 ms |
37368 KB |
Output is correct |
6 |
Correct |
34 ms |
37368 KB |
Output is correct |
7 |
Correct |
33 ms |
37368 KB |
Output is correct |
8 |
Correct |
33 ms |
37356 KB |
Output is correct |
9 |
Correct |
32 ms |
37376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
34 ms |
37376 KB |
Output is correct |
2 |
Correct |
34 ms |
37340 KB |
Output is correct |
3 |
Correct |
33 ms |
37372 KB |
Output is correct |
4 |
Correct |
33 ms |
37340 KB |
Output is correct |
5 |
Correct |
33 ms |
37368 KB |
Output is correct |
6 |
Correct |
34 ms |
37368 KB |
Output is correct |
7 |
Correct |
33 ms |
37368 KB |
Output is correct |
8 |
Correct |
33 ms |
37356 KB |
Output is correct |
9 |
Correct |
32 ms |
37376 KB |
Output is correct |
10 |
Correct |
56 ms |
38164 KB |
Output is correct |
11 |
Correct |
39 ms |
38136 KB |
Output is correct |
12 |
Correct |
40 ms |
37980 KB |
Output is correct |
13 |
Correct |
39 ms |
38392 KB |
Output is correct |
14 |
Correct |
40 ms |
38264 KB |
Output is correct |
15 |
Correct |
39 ms |
38136 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
818 ms |
85564 KB |
Output is correct |
2 |
Correct |
601 ms |
90768 KB |
Output is correct |
3 |
Correct |
558 ms |
86156 KB |
Output is correct |
4 |
Correct |
593 ms |
84700 KB |
Output is correct |
5 |
Correct |
618 ms |
84776 KB |
Output is correct |
6 |
Correct |
674 ms |
85368 KB |
Output is correct |
7 |
Correct |
669 ms |
82476 KB |
Output is correct |
8 |
Correct |
553 ms |
90616 KB |
Output is correct |
9 |
Correct |
516 ms |
85336 KB |
Output is correct |
10 |
Correct |
544 ms |
83064 KB |
Output is correct |
11 |
Correct |
520 ms |
83320 KB |
Output is correct |
12 |
Correct |
592 ms |
83712 KB |
Output is correct |
13 |
Correct |
692 ms |
97904 KB |
Output is correct |
14 |
Correct |
612 ms |
97752 KB |
Output is correct |
15 |
Correct |
593 ms |
97912 KB |
Output is correct |
16 |
Correct |
622 ms |
97912 KB |
Output is correct |
17 |
Correct |
695 ms |
82344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
34 ms |
37376 KB |
Output is correct |
2 |
Correct |
34 ms |
37340 KB |
Output is correct |
3 |
Correct |
33 ms |
37372 KB |
Output is correct |
4 |
Correct |
33 ms |
37340 KB |
Output is correct |
5 |
Correct |
33 ms |
37368 KB |
Output is correct |
6 |
Correct |
34 ms |
37368 KB |
Output is correct |
7 |
Correct |
33 ms |
37368 KB |
Output is correct |
8 |
Correct |
33 ms |
37356 KB |
Output is correct |
9 |
Correct |
32 ms |
37376 KB |
Output is correct |
10 |
Correct |
56 ms |
38164 KB |
Output is correct |
11 |
Correct |
39 ms |
38136 KB |
Output is correct |
12 |
Correct |
40 ms |
37980 KB |
Output is correct |
13 |
Correct |
39 ms |
38392 KB |
Output is correct |
14 |
Correct |
40 ms |
38264 KB |
Output is correct |
15 |
Correct |
39 ms |
38136 KB |
Output is correct |
16 |
Correct |
818 ms |
85564 KB |
Output is correct |
17 |
Correct |
601 ms |
90768 KB |
Output is correct |
18 |
Correct |
558 ms |
86156 KB |
Output is correct |
19 |
Correct |
593 ms |
84700 KB |
Output is correct |
20 |
Correct |
618 ms |
84776 KB |
Output is correct |
21 |
Correct |
674 ms |
85368 KB |
Output is correct |
22 |
Correct |
669 ms |
82476 KB |
Output is correct |
23 |
Correct |
553 ms |
90616 KB |
Output is correct |
24 |
Correct |
516 ms |
85336 KB |
Output is correct |
25 |
Correct |
544 ms |
83064 KB |
Output is correct |
26 |
Correct |
520 ms |
83320 KB |
Output is correct |
27 |
Correct |
592 ms |
83712 KB |
Output is correct |
28 |
Correct |
692 ms |
97904 KB |
Output is correct |
29 |
Correct |
612 ms |
97752 KB |
Output is correct |
30 |
Correct |
593 ms |
97912 KB |
Output is correct |
31 |
Correct |
622 ms |
97912 KB |
Output is correct |
32 |
Correct |
695 ms |
82344 KB |
Output is correct |
33 |
Correct |
791 ms |
86940 KB |
Output is correct |
34 |
Correct |
321 ms |
67784 KB |
Output is correct |
35 |
Correct |
1025 ms |
90616 KB |
Output is correct |
36 |
Correct |
765 ms |
86724 KB |
Output is correct |
37 |
Correct |
930 ms |
89904 KB |
Output is correct |
38 |
Correct |
755 ms |
87800 KB |
Output is correct |
39 |
Correct |
583 ms |
103032 KB |
Output is correct |
40 |
Correct |
718 ms |
91424 KB |
Output is correct |
41 |
Correct |
669 ms |
87608 KB |
Output is correct |
42 |
Correct |
653 ms |
83908 KB |
Output is correct |
43 |
Correct |
752 ms |
95220 KB |
Output is correct |
44 |
Correct |
684 ms |
88332 KB |
Output is correct |
45 |
Correct |
567 ms |
102948 KB |
Output is correct |
46 |
Correct |
629 ms |
102800 KB |
Output is correct |
47 |
Correct |
623 ms |
98136 KB |
Output is correct |
48 |
Correct |
618 ms |
97768 KB |
Output is correct |
49 |
Correct |
623 ms |
97988 KB |
Output is correct |
50 |
Correct |
675 ms |
97996 KB |
Output is correct |
51 |
Correct |
712 ms |
88844 KB |
Output is correct |
52 |
Correct |
677 ms |
88696 KB |
Output is correct |