//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "werewolf.h"
#define vi vector<int>
#define pb push_back
using namespace std;
const int MAXN = 2e5 + 50;
vi adj[MAXN], ltree[MAXN], rtree[MAXN], lArr[MAXN], rArr[MAXN];
int par[MAXN], sz[MAXN], lA[MAXN], rA[MAXN], ind[MAXN];
int stL[MAXN], enL[MAXN], stR[MAXN], enR[MAXN];
int lPar[18][MAXN], rPar[18][MAXN];
set<int> comp[MAXN];
int n, m, q, t, BIT[MAXN], tmp[2*MAXN];
void add(int ind, int v) {
ind++;
while (ind < MAXN) {
BIT[ind] += v;
ind += ind & -ind;
}
}
int sum(int ind) {
ind++;
int ret = 0;
while (ind > 0) {
ret += BIT[ind];
ind -= ind & -ind;
}
return ret;
}
void ldfs(int u, int p) {
stL[u] = t;
lA[t++] = u;
for (int v: ltree[u])
if (v != p) {
ldfs(v, u);
lPar[0][v] = u;
}
enL[u] = t - 1;
}
void rdfs(int u, int p) {
stR[u] = t;
rA[t++] = u;
for (int v: rtree[u])
if (v != p) {
rdfs(v, u);
rPar[0][v] = u;
}
enR[u] = t - 1;
}
int qry(int x) {
return x == par[x] ? x : par[x] = qry(par[x]);
}
void join(int x, int y) {
x = qry(x), y = qry(y);
if (x == y) return;
if (sz[x] > sz[y]) swap(x, y);
par[x] = y;
sz[y] += sz[x];
comp[y].insert(comp[x].begin(), comp[x].end());
comp[x].clear();
}
void init() {
for (int i = 0; i < n; i++) {
par[i] = i;
sz[i] = 1;
comp[i] = {i};
}
}
vi check_validity(int N, vi x, vi y, vi s, vi e, vi l, vi r) {
n = N, m = x.size(), q = l.size();
for (int i = 0; i < m; i++) {
adj[x[i]].pb(y[i]);
adj[y[i]].pb(x[i]);
}
init();
for (int i = 0; i < n; i++) { // r
for (int v: adj[i]) {
if (v > i || qry(i) == qry(v)) continue;
int u = *(--comp[qry(v)].end());
join(i, u);
rtree[i].pb(u);
rtree[u].pb(i);
}
}
init();
for (int i = n - 1; i >= 0; i--) { // l
for (int v: adj[i]) {
if (v < i || qry(i) == qry(v)) continue;
int u = *(comp[qry(v)].begin());
join(i, u);
ltree[i].pb(u);
ltree[u].pb(i);
}
}
for (int i = 0; i < 18; i++)
fill(lPar[i], lPar[i] + MAXN, 0), fill(rPar[i], rPar[i] + MAXN, n - 1);
t = 0;
ldfs(0, -1);
t = 0;
rdfs(n - 1, -1);
for (int i = 1; i < 18; i++)
for (int j = 0; j < n; j++)
lPar[i][j] = lPar[i - 1][lPar[i - 1][j]],
rPar[i][j] = rPar[i - 1][rPar[i - 1][j]];
for (int i = 0; i < n; i++)
ind[rA[i]] = i;
vi ret;
for (int i = 0; i < q; i++) {
ret.pb(0);
int u = s[i];
for (int j = 17; j >= 0; j--)
if (lPar[j][u] >= l[i])
u = lPar[j][u];
lArr[stL[u]].pb(i);
rArr[enL[u]].pb(i);
}
for (int i = 0; i < n; i++) {
for (int j: lArr[i]) {
int u = e[j];
for (int k = 17; k >= 0; k--)
if (rPar[k][u] <= r[j])
u = rPar[k][u];
tmp[j] = sum(enR[u]) - sum(stR[u] - 1);
}
add(ind[lA[i]], 1);
for (int j: rArr[i]) {
int u = e[j];
for (int k = 17; k >= 0; k--)
if (rPar[k][u] <= r[j])
u = rPar[k][u];
if (sum(enR[u]) - sum(stR[u] - 1) != tmp[j])
ret[j] = 1;
else
ret[j] = 0;
}
}
return ret;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
71 ms |
61560 KB |
Output is correct |
2 |
Correct |
62 ms |
61560 KB |
Output is correct |
3 |
Correct |
74 ms |
61560 KB |
Output is correct |
4 |
Correct |
62 ms |
61560 KB |
Output is correct |
5 |
Correct |
58 ms |
61560 KB |
Output is correct |
6 |
Correct |
58 ms |
61432 KB |
Output is correct |
7 |
Correct |
67 ms |
61648 KB |
Output is correct |
8 |
Correct |
60 ms |
61532 KB |
Output is correct |
9 |
Correct |
61 ms |
61432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
71 ms |
61560 KB |
Output is correct |
2 |
Correct |
62 ms |
61560 KB |
Output is correct |
3 |
Correct |
74 ms |
61560 KB |
Output is correct |
4 |
Correct |
62 ms |
61560 KB |
Output is correct |
5 |
Correct |
58 ms |
61560 KB |
Output is correct |
6 |
Correct |
58 ms |
61432 KB |
Output is correct |
7 |
Correct |
67 ms |
61648 KB |
Output is correct |
8 |
Correct |
60 ms |
61532 KB |
Output is correct |
9 |
Correct |
61 ms |
61432 KB |
Output is correct |
10 |
Correct |
70 ms |
62296 KB |
Output is correct |
11 |
Correct |
85 ms |
62268 KB |
Output is correct |
12 |
Correct |
89 ms |
62308 KB |
Output is correct |
13 |
Correct |
74 ms |
62456 KB |
Output is correct |
14 |
Correct |
66 ms |
62456 KB |
Output is correct |
15 |
Correct |
70 ms |
62456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3907 ms |
114292 KB |
Output is correct |
2 |
Correct |
2537 ms |
116132 KB |
Output is correct |
3 |
Correct |
2501 ms |
112772 KB |
Output is correct |
4 |
Correct |
2795 ms |
112908 KB |
Output is correct |
5 |
Correct |
2766 ms |
113104 KB |
Output is correct |
6 |
Correct |
3466 ms |
113904 KB |
Output is correct |
7 |
Correct |
3880 ms |
113920 KB |
Output is correct |
8 |
Correct |
2090 ms |
116076 KB |
Output is correct |
9 |
Correct |
1266 ms |
112616 KB |
Output is correct |
10 |
Correct |
1271 ms |
112244 KB |
Output is correct |
11 |
Correct |
1568 ms |
112356 KB |
Output is correct |
12 |
Correct |
2059 ms |
113752 KB |
Output is correct |
13 |
Correct |
2449 ms |
121760 KB |
Output is correct |
14 |
Correct |
2396 ms |
120284 KB |
Output is correct |
15 |
Correct |
2582 ms |
121572 KB |
Output is correct |
16 |
Correct |
2774 ms |
121056 KB |
Output is correct |
17 |
Correct |
3686 ms |
113584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
71 ms |
61560 KB |
Output is correct |
2 |
Correct |
62 ms |
61560 KB |
Output is correct |
3 |
Correct |
74 ms |
61560 KB |
Output is correct |
4 |
Correct |
62 ms |
61560 KB |
Output is correct |
5 |
Correct |
58 ms |
61560 KB |
Output is correct |
6 |
Correct |
58 ms |
61432 KB |
Output is correct |
7 |
Correct |
67 ms |
61648 KB |
Output is correct |
8 |
Correct |
60 ms |
61532 KB |
Output is correct |
9 |
Correct |
61 ms |
61432 KB |
Output is correct |
10 |
Correct |
70 ms |
62296 KB |
Output is correct |
11 |
Correct |
85 ms |
62268 KB |
Output is correct |
12 |
Correct |
89 ms |
62308 KB |
Output is correct |
13 |
Correct |
74 ms |
62456 KB |
Output is correct |
14 |
Correct |
66 ms |
62456 KB |
Output is correct |
15 |
Correct |
70 ms |
62456 KB |
Output is correct |
16 |
Correct |
3907 ms |
114292 KB |
Output is correct |
17 |
Correct |
2537 ms |
116132 KB |
Output is correct |
18 |
Correct |
2501 ms |
112772 KB |
Output is correct |
19 |
Correct |
2795 ms |
112908 KB |
Output is correct |
20 |
Correct |
2766 ms |
113104 KB |
Output is correct |
21 |
Correct |
3466 ms |
113904 KB |
Output is correct |
22 |
Correct |
3880 ms |
113920 KB |
Output is correct |
23 |
Correct |
2090 ms |
116076 KB |
Output is correct |
24 |
Correct |
1266 ms |
112616 KB |
Output is correct |
25 |
Correct |
1271 ms |
112244 KB |
Output is correct |
26 |
Correct |
1568 ms |
112356 KB |
Output is correct |
27 |
Correct |
2059 ms |
113752 KB |
Output is correct |
28 |
Correct |
2449 ms |
121760 KB |
Output is correct |
29 |
Correct |
2396 ms |
120284 KB |
Output is correct |
30 |
Correct |
2582 ms |
121572 KB |
Output is correct |
31 |
Correct |
2774 ms |
121056 KB |
Output is correct |
32 |
Correct |
3686 ms |
113584 KB |
Output is correct |
33 |
Correct |
3547 ms |
124280 KB |
Output is correct |
34 |
Correct |
412 ms |
95220 KB |
Output is correct |
35 |
Correct |
3294 ms |
126996 KB |
Output is correct |
36 |
Correct |
3449 ms |
123228 KB |
Output is correct |
37 |
Correct |
3310 ms |
125932 KB |
Output is correct |
38 |
Correct |
3496 ms |
124060 KB |
Output is correct |
39 |
Correct |
2495 ms |
135608 KB |
Output is correct |
40 |
Correct |
2346 ms |
132864 KB |
Output is correct |
41 |
Correct |
2179 ms |
123260 KB |
Output is correct |
42 |
Correct |
2008 ms |
120288 KB |
Output is correct |
43 |
Correct |
2599 ms |
129900 KB |
Output is correct |
44 |
Correct |
2788 ms |
124080 KB |
Output is correct |
45 |
Correct |
1691 ms |
132592 KB |
Output is correct |
46 |
Correct |
2113 ms |
132488 KB |
Output is correct |
47 |
Correct |
2658 ms |
129336 KB |
Output is correct |
48 |
Correct |
2485 ms |
128424 KB |
Output is correct |
49 |
Correct |
2676 ms |
129836 KB |
Output is correct |
50 |
Correct |
2608 ms |
128564 KB |
Output is correct |
51 |
Correct |
1891 ms |
134596 KB |
Output is correct |
52 |
Correct |
1825 ms |
134492 KB |
Output is correct |