#include "werewolf.h"
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;
vector<int> dsu_tree[2][200000], graph[200000];
int N, p[2][20][200000], timer, cmp[2][200000], order[2][200000];
pair<int, int> bounds[2][200000];
void dfs(int node, int t) {
bounds[t][node] = {timer, timer};
order[t][timer] = node;
timer++;
FOR(i, 1, 20) {
if (p[t][i - 1][node] == -1) break;
p[t][i][node] = p[t][i - 1][p[t][i - 1][node]];
}
for (int i : dsu_tree[t][node]) {
p[t][0][i] = node;
dfs(i, t);
bounds[t][node].second =
max(bounds[t][node].second, bounds[t][i].second);
}
}
int find(int a, int t) {
while (a != cmp[t][a]) cmp[t][a] = cmp[t][cmp[t][a]], a = cmp[t][a];
return a;
}
void onion(int a, int b, int t) {
cmp[t][find(a, t)] = cmp[t][find(b, t)];
}
vector<int> segtree[800000];
void build(int node = 1, int l = 0, int r = N - 1) {
if (l == r) segtree[node] = {bounds[0][order[1][l]].first};
else {
int mid = (l + r) / 2;
build(node * 2, l, mid);
build(node * 2 + 1, mid + 1, r);
int lptr = 0, rptr = 0;
int lsz = segtree[node * 2].size(), rsz = segtree[node * 2 + 1].size();
while (lptr < lsz && rptr < rsz) {
if (segtree[node * 2][lptr] < segtree[node * 2 + 1][rptr]) {
segtree[node].push_back(segtree[node * 2][lptr++]);
} else {
segtree[node].push_back(segtree[node * 2 + 1][rptr++]);
}
}
while (lptr < lsz) segtree[node].push_back(segtree[node * 2][lptr++]);
while (rptr < rsz) segtree[node].push_back(segtree[node * 2 + 1][rptr++]);
}
}
bool query(int a, int b, int x, int y, int node = 1, int l = 0, int r = N - 1) {
if (r < a || l > b) return false;
if (r <= b && l >= a)
return (
upper_bound(segtree[node].begin(), segtree[node].end(), y) -
lower_bound(segtree[node].begin(), segtree[node].end(), x) !=
0);
int mid = (l + r) / 2;
return (query(a, b, x, y, node * 2, l, mid) ||
query(a, b, x, y, node * 2 + 1, mid + 1, r));
}
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;
int Q = S.size();
vector<int> A(Q);
FOR(i, 0, N) cmp[0][i] = cmp[1][i] = i;
FOR(i, 0, X.size()) {
graph[X[i]].push_back(Y[i]);
graph[Y[i]].push_back(X[i]);
}
for (int i = N - 1; ~i; i--)
for (int j : graph[i])
if (j > i && find(j, 0) != find(i, 0)) {
dsu_tree[0][i].push_back(find(j, 0));
onion(j, i, 0);
}
for (int i = 0; i < N; i++)
for (int j : graph[i])
if (j < i && find(j, 1) != find(i, 1)) {
dsu_tree[1][i].push_back(find(j, 1));
onion(j, i, 1);
}
memset(p, -1, sizeof(p));
timer = 0;
dfs(0, 0);
timer = 0;
dfs(N - 1, 1);
build();
FOR(i, 0, Q) {
int X = S[i], Y = E[i];
for (int j = 19; ~j; j--) {
if (~p[0][j][X] && p[0][j][X] >= L[i]) X = p[0][j][X];
if (~p[1][j][Y] && p[1][j][Y] <= R[i]) Y = p[1][j][Y];
}
A[i] = query(bounds[1][Y].first, bounds[1][Y].second, bounds[0][X].first, bounds[0][X].second);
}
return A;
}
Compilation message
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:3:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i, x, y) for (int i = x; i < y; i++)
werewolf.cpp:78:9:
FOR(i, 0, X.size()) {
~~~~~~~~~~~~~~
werewolf.cpp:78:5: note: in expansion of macro 'FOR'
FOR(i, 0, X.size()) {
^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
60 ms |
64504 KB |
Output is correct |
2 |
Correct |
59 ms |
64604 KB |
Output is correct |
3 |
Correct |
60 ms |
64504 KB |
Output is correct |
4 |
Correct |
67 ms |
64632 KB |
Output is correct |
5 |
Correct |
60 ms |
64504 KB |
Output is correct |
6 |
Correct |
60 ms |
64632 KB |
Output is correct |
7 |
Correct |
59 ms |
64504 KB |
Output is correct |
8 |
Correct |
60 ms |
64632 KB |
Output is correct |
9 |
Correct |
61 ms |
64632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
60 ms |
64504 KB |
Output is correct |
2 |
Correct |
59 ms |
64604 KB |
Output is correct |
3 |
Correct |
60 ms |
64504 KB |
Output is correct |
4 |
Correct |
67 ms |
64632 KB |
Output is correct |
5 |
Correct |
60 ms |
64504 KB |
Output is correct |
6 |
Correct |
60 ms |
64632 KB |
Output is correct |
7 |
Correct |
59 ms |
64504 KB |
Output is correct |
8 |
Correct |
60 ms |
64632 KB |
Output is correct |
9 |
Correct |
61 ms |
64632 KB |
Output is correct |
10 |
Correct |
68 ms |
65532 KB |
Output is correct |
11 |
Correct |
79 ms |
65480 KB |
Output is correct |
12 |
Correct |
74 ms |
65400 KB |
Output is correct |
13 |
Correct |
75 ms |
65660 KB |
Output is correct |
14 |
Correct |
68 ms |
65656 KB |
Output is correct |
15 |
Correct |
76 ms |
65528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1071 ms |
127184 KB |
Output is correct |
2 |
Correct |
1063 ms |
128996 KB |
Output is correct |
3 |
Correct |
924 ms |
125296 KB |
Output is correct |
4 |
Correct |
1000 ms |
123632 KB |
Output is correct |
5 |
Correct |
1068 ms |
123504 KB |
Output is correct |
6 |
Correct |
1148 ms |
123376 KB |
Output is correct |
7 |
Correct |
1070 ms |
123376 KB |
Output is correct |
8 |
Correct |
954 ms |
129136 KB |
Output is correct |
9 |
Correct |
833 ms |
125360 KB |
Output is correct |
10 |
Correct |
659 ms |
123760 KB |
Output is correct |
11 |
Correct |
733 ms |
123504 KB |
Output is correct |
12 |
Correct |
894 ms |
124240 KB |
Output is correct |
13 |
Correct |
1188 ms |
136304 KB |
Output is correct |
14 |
Correct |
1153 ms |
136048 KB |
Output is correct |
15 |
Correct |
1154 ms |
136004 KB |
Output is correct |
16 |
Correct |
1136 ms |
136032 KB |
Output is correct |
17 |
Correct |
1071 ms |
124052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
60 ms |
64504 KB |
Output is correct |
2 |
Correct |
59 ms |
64604 KB |
Output is correct |
3 |
Correct |
60 ms |
64504 KB |
Output is correct |
4 |
Correct |
67 ms |
64632 KB |
Output is correct |
5 |
Correct |
60 ms |
64504 KB |
Output is correct |
6 |
Correct |
60 ms |
64632 KB |
Output is correct |
7 |
Correct |
59 ms |
64504 KB |
Output is correct |
8 |
Correct |
60 ms |
64632 KB |
Output is correct |
9 |
Correct |
61 ms |
64632 KB |
Output is correct |
10 |
Correct |
68 ms |
65532 KB |
Output is correct |
11 |
Correct |
79 ms |
65480 KB |
Output is correct |
12 |
Correct |
74 ms |
65400 KB |
Output is correct |
13 |
Correct |
75 ms |
65660 KB |
Output is correct |
14 |
Correct |
68 ms |
65656 KB |
Output is correct |
15 |
Correct |
76 ms |
65528 KB |
Output is correct |
16 |
Correct |
1071 ms |
127184 KB |
Output is correct |
17 |
Correct |
1063 ms |
128996 KB |
Output is correct |
18 |
Correct |
924 ms |
125296 KB |
Output is correct |
19 |
Correct |
1000 ms |
123632 KB |
Output is correct |
20 |
Correct |
1068 ms |
123504 KB |
Output is correct |
21 |
Correct |
1148 ms |
123376 KB |
Output is correct |
22 |
Correct |
1070 ms |
123376 KB |
Output is correct |
23 |
Correct |
954 ms |
129136 KB |
Output is correct |
24 |
Correct |
833 ms |
125360 KB |
Output is correct |
25 |
Correct |
659 ms |
123760 KB |
Output is correct |
26 |
Correct |
733 ms |
123504 KB |
Output is correct |
27 |
Correct |
894 ms |
124240 KB |
Output is correct |
28 |
Correct |
1188 ms |
136304 KB |
Output is correct |
29 |
Correct |
1153 ms |
136048 KB |
Output is correct |
30 |
Correct |
1154 ms |
136004 KB |
Output is correct |
31 |
Correct |
1136 ms |
136032 KB |
Output is correct |
32 |
Correct |
1071 ms |
124052 KB |
Output is correct |
33 |
Correct |
1399 ms |
125036 KB |
Output is correct |
34 |
Correct |
427 ms |
85212 KB |
Output is correct |
35 |
Correct |
1422 ms |
128736 KB |
Output is correct |
36 |
Correct |
1324 ms |
125040 KB |
Output is correct |
37 |
Correct |
1493 ms |
127652 KB |
Output is correct |
38 |
Correct |
1357 ms |
125900 KB |
Output is correct |
39 |
Correct |
1486 ms |
141180 KB |
Output is correct |
40 |
Correct |
1233 ms |
133176 KB |
Output is correct |
41 |
Correct |
1072 ms |
127096 KB |
Output is correct |
42 |
Correct |
769 ms |
125168 KB |
Output is correct |
43 |
Correct |
1167 ms |
133876 KB |
Output is correct |
44 |
Correct |
1285 ms |
127860 KB |
Output is correct |
45 |
Correct |
1059 ms |
140904 KB |
Output is correct |
46 |
Correct |
1040 ms |
140784 KB |
Output is correct |
47 |
Correct |
1239 ms |
135920 KB |
Output is correct |
48 |
Correct |
1181 ms |
135872 KB |
Output is correct |
49 |
Correct |
1151 ms |
135800 KB |
Output is correct |
50 |
Correct |
1181 ms |
135612 KB |
Output is correct |
51 |
Correct |
1220 ms |
132576 KB |
Output is correct |
52 |
Correct |
1174 ms |
132308 KB |
Output is correct |