# include <bits/stdc++.h>
# include "werewolf.h"
using namespace std;
const int maxn = 2e5 + 2;
int p[2][maxn], timer, tin[3][maxn], tout[3][maxn], up[3][19][maxn], pos[maxn], fen[maxn];
vector <int> g[3][maxn];
int f_s(int tp, int v){
return p[tp][v] == v?v:p[tp][v] = f_s(tp, p[tp][v]);
}
void dfs(int tp, int v, int pr){
tin[tp][v] = ++ timer;
up[tp][0][v] = pr;
for(int i = 1; i <= 18; i ++)
up[tp][i][v] = up[tp][i - 1][ up[tp][i - 1][v] ];
for(int to : g[tp][v]){
if(to == pr)
continue;
dfs(tp, to, v);
}
tout[tp][v] = timer;
}
void upd(int pos){
for(; pos < maxn; pos |= pos + 1)
fen[pos] ++;
}
int get(int r){
int ret = 0;
for(; r > 0; r = (r & (r + 1)) - 1)
ret += fen[r];
return ret;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
int Q = S.size(), M = X.size();
vector<int> A(Q);
for(int i = 0; i < M; i ++){
g[0][X[i]].push_back(Y[i]);
g[0][Y[i]].push_back(X[i]);
}
for(int i = 0; i < N; i ++)
p[0][i] = p[1][i] = i;
for(int i = N - 1; i >= 0; i --){
for(int to : g[0][i]){
if(to < i || f_s(0, i) == f_s(0, to))
continue;
int a = f_s(0, i), b = f_s(0, to);
g[1][a].push_back(b);
p[0][b] = a;
}
}
for(int i = 0; i < N; i ++){
for(int to : g[0][i]){
if(to > i || f_s(1, i) == f_s(1, to))
continue;
int a = f_s(1, i), b = f_s(1, to);
g[2][a].push_back(b);
p[1][b] = a;
}
}
dfs(1, f_s(0, 0), f_s(0, 0));
timer = 0;
dfs(2, f_s(1, 0), f_s(1, 0));
vector < pair <int, pair <int, int> > > qe;
for(int i = 0; i < Q; i ++){
int s = S[i], e = E[i], l = L[i], r = R[i];
for(int j = 18; j >= 0; j --){
if(up[1][j][s] >= l)
s = up[1][j][s];
}
for(int j = 18; j >= 0; j --){
if(up[2][j][e] <= r)
e = up[2][j][e];
}
qe.push_back({tin[1][s] - 1, {-(i + 1), e}});
qe.push_back({tout[1][s], {i + 1, e}});
}
sort(qe.begin(), qe.end());
for(int i = 0; i < N; i ++)
pos[ tin[1][i] - 1 ] = tin[2][i];
int pt = 0;
for(int i = 0; i < qe.size(); i ++){
int p = qe[i].first, id = qe[i].second.first, v = qe[i].second.second;
while(pt < p)
upd(pos[pt ++]);
if(id < 0)
A[abs(id) - 1] -= get(tout[2][v]) - get(tin[2][v] - 1);
else
A[abs(id) - 1] += get(tout[2][v]) - get(tin[2][v] - 1);
}
for(int i = 0; i < Q; i ++)
A[i] = (A[i] > 0);
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:99:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < qe.size(); i ++){
~~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
14720 KB |
Output is correct |
2 |
Correct |
17 ms |
14720 KB |
Output is correct |
3 |
Correct |
14 ms |
14720 KB |
Output is correct |
4 |
Correct |
14 ms |
14720 KB |
Output is correct |
5 |
Correct |
15 ms |
14720 KB |
Output is correct |
6 |
Correct |
16 ms |
14720 KB |
Output is correct |
7 |
Correct |
16 ms |
14720 KB |
Output is correct |
8 |
Correct |
16 ms |
14720 KB |
Output is correct |
9 |
Correct |
32 ms |
14840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
14720 KB |
Output is correct |
2 |
Correct |
17 ms |
14720 KB |
Output is correct |
3 |
Correct |
14 ms |
14720 KB |
Output is correct |
4 |
Correct |
14 ms |
14720 KB |
Output is correct |
5 |
Correct |
15 ms |
14720 KB |
Output is correct |
6 |
Correct |
16 ms |
14720 KB |
Output is correct |
7 |
Correct |
16 ms |
14720 KB |
Output is correct |
8 |
Correct |
16 ms |
14720 KB |
Output is correct |
9 |
Correct |
32 ms |
14840 KB |
Output is correct |
10 |
Correct |
22 ms |
15872 KB |
Output is correct |
11 |
Correct |
23 ms |
15872 KB |
Output is correct |
12 |
Correct |
23 ms |
15872 KB |
Output is correct |
13 |
Correct |
22 ms |
16048 KB |
Output is correct |
14 |
Correct |
21 ms |
16000 KB |
Output is correct |
15 |
Correct |
22 ms |
15952 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1299 ms |
80264 KB |
Output is correct |
2 |
Correct |
1079 ms |
94128 KB |
Output is correct |
3 |
Correct |
1079 ms |
89972 KB |
Output is correct |
4 |
Correct |
1156 ms |
88540 KB |
Output is correct |
5 |
Correct |
1209 ms |
88436 KB |
Output is correct |
6 |
Correct |
1342 ms |
88164 KB |
Output is correct |
7 |
Correct |
1196 ms |
88268 KB |
Output is correct |
8 |
Correct |
965 ms |
93804 KB |
Output is correct |
9 |
Correct |
727 ms |
90068 KB |
Output is correct |
10 |
Correct |
603 ms |
88492 KB |
Output is correct |
11 |
Correct |
593 ms |
88352 KB |
Output is correct |
12 |
Correct |
608 ms |
88096 KB |
Output is correct |
13 |
Correct |
1108 ms |
100060 KB |
Output is correct |
14 |
Correct |
1123 ms |
100064 KB |
Output is correct |
15 |
Correct |
1155 ms |
100060 KB |
Output is correct |
16 |
Correct |
1165 ms |
99960 KB |
Output is correct |
17 |
Correct |
1420 ms |
88116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
14720 KB |
Output is correct |
2 |
Correct |
17 ms |
14720 KB |
Output is correct |
3 |
Correct |
14 ms |
14720 KB |
Output is correct |
4 |
Correct |
14 ms |
14720 KB |
Output is correct |
5 |
Correct |
15 ms |
14720 KB |
Output is correct |
6 |
Correct |
16 ms |
14720 KB |
Output is correct |
7 |
Correct |
16 ms |
14720 KB |
Output is correct |
8 |
Correct |
16 ms |
14720 KB |
Output is correct |
9 |
Correct |
32 ms |
14840 KB |
Output is correct |
10 |
Correct |
22 ms |
15872 KB |
Output is correct |
11 |
Correct |
23 ms |
15872 KB |
Output is correct |
12 |
Correct |
23 ms |
15872 KB |
Output is correct |
13 |
Correct |
22 ms |
16048 KB |
Output is correct |
14 |
Correct |
21 ms |
16000 KB |
Output is correct |
15 |
Correct |
22 ms |
15952 KB |
Output is correct |
16 |
Correct |
1299 ms |
80264 KB |
Output is correct |
17 |
Correct |
1079 ms |
94128 KB |
Output is correct |
18 |
Correct |
1079 ms |
89972 KB |
Output is correct |
19 |
Correct |
1156 ms |
88540 KB |
Output is correct |
20 |
Correct |
1209 ms |
88436 KB |
Output is correct |
21 |
Correct |
1342 ms |
88164 KB |
Output is correct |
22 |
Correct |
1196 ms |
88268 KB |
Output is correct |
23 |
Correct |
965 ms |
93804 KB |
Output is correct |
24 |
Correct |
727 ms |
90068 KB |
Output is correct |
25 |
Correct |
603 ms |
88492 KB |
Output is correct |
26 |
Correct |
593 ms |
88352 KB |
Output is correct |
27 |
Correct |
608 ms |
88096 KB |
Output is correct |
28 |
Correct |
1108 ms |
100060 KB |
Output is correct |
29 |
Correct |
1123 ms |
100064 KB |
Output is correct |
30 |
Correct |
1155 ms |
100060 KB |
Output is correct |
31 |
Correct |
1165 ms |
99960 KB |
Output is correct |
32 |
Correct |
1420 ms |
88116 KB |
Output is correct |
33 |
Correct |
1383 ms |
89420 KB |
Output is correct |
34 |
Correct |
396 ms |
46316 KB |
Output is correct |
35 |
Correct |
1395 ms |
90008 KB |
Output is correct |
36 |
Correct |
1388 ms |
86236 KB |
Output is correct |
37 |
Correct |
1431 ms |
89088 KB |
Output is correct |
38 |
Correct |
1424 ms |
86928 KB |
Output is correct |
39 |
Correct |
1278 ms |
102184 KB |
Output is correct |
40 |
Correct |
1230 ms |
94244 KB |
Output is correct |
41 |
Correct |
811 ms |
88184 KB |
Output is correct |
42 |
Correct |
737 ms |
86364 KB |
Output is correct |
43 |
Correct |
1148 ms |
94716 KB |
Output is correct |
44 |
Correct |
1016 ms |
88924 KB |
Output is correct |
45 |
Correct |
899 ms |
102192 KB |
Output is correct |
46 |
Correct |
884 ms |
102044 KB |
Output is correct |
47 |
Correct |
1116 ms |
97044 KB |
Output is correct |
48 |
Correct |
1081 ms |
96908 KB |
Output is correct |
49 |
Correct |
1060 ms |
97120 KB |
Output is correct |
50 |
Correct |
1093 ms |
97112 KB |
Output is correct |
51 |
Correct |
1207 ms |
94076 KB |
Output is correct |
52 |
Correct |
1115 ms |
93788 KB |
Output is correct |