#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, pii> pipii;
vector<int> g[200005], g2[200005], g3[200005];
int par2[19][200005], par3[19][200005];
int p[200005];
int mapp[200005];
int sz[200005];
int root(int a){
return p[a] == a?a:(p[a]=root(p[a]));
}
void merge(int a, int b, int t){
a = root(a), b = root(b);
if(a != b){
p[a] = b;
if(t == 0) sz[b] = min(sz[b], sz[a]);
else sz[b] = max(sz[b], sz[a]);
}
}
int arr2[200005], arr3[200005], j = 1;
int s2[200005], e2[200005], s3[200005], e3[200005];
void dfs2(int u, int p){
arr2[j++] = u;
par2[0][u] = p;
s2[u] = j-1;
for(int i=0;i<g2[u].size();i++){
int v = g2[u][i];
dfs2(v, u);
}
e2[u] = j-1;
}
void dfs3(int u, int p){
arr3[j++] = u;
par3[0][u] = p;
s3[u] = j-1;
for(int i=0;i<g3[u].size();i++){
int v = g3[u][i];
dfs3(v, u);
}
e3[u] = j-1;
}
set<int> dp[200005];
set<int>::iterator its;
vector<pipii> cur[200005];
vector<int> ans;
void dfs(int u, int p){
dp[u].insert(mapp[u]);
for(int i=0;i<g3[u].size();i++){
int v = g3[u][i];
dfs(v, u);
if(dp[u].size() < dp[v].size()) swap(dp[u], dp[v]);
for(its = dp[v].begin();its != dp[v].end();its++) dp[u].insert(*its);
}
for(int i=0;i<cur[u].size();i++){
int j = cur[u][i].first;
int l = cur[u][i].second.first, r = cur[u][i].second.second;
its = dp[u].lower_bound(l);
if(l <= *its && *its <= r) ans[j] = 1;
else ans[j] = 0;
}
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y, std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R){
int n = N;
int m = X.size();
int q = S.size();
ans.resize(q);
for(int i=0;i<m;i++){
int a, b;
a = X[i]+1, b = Y[i]+1;
g[a].push_back(b);
g[b].push_back(a);
}
for(int i=1;i<=n;i++) p[i] = i, sz[i] = i;
for(int i=n;i>=1;i--){
for(int j=0;j<g[i].size();j++){
int v = g[i][j];
if(v >= i){
if(root(i) != root(v)){
int r = root(v);
g2[i].push_back(sz[r]);
}
merge(i, v, 0);
}
}
}
for(int i=1;i<=n;i++) p[i] = i, sz[i] = i;
for(int i=1;i<=n;i++){
for(int j=0;j<g[i].size();j++){
int v = g[i][j];
if(v <= i){
if(root(i) != root(v)){
int r = root(v);
g3[i].push_back(sz[r]);
}
merge(i, v, 1);
}
}
}
j = 1;
dfs2(1, 0); // human
j = 1;
dfs3(n, 0); // wolf
j--;
for(int i=1;i<=n;i++){
mapp[arr2[i]] = i;
}
for(int j=1;j<=18;j++){
for(int i=1;i<=n;i++){
if(par2[j-1][i] != 0) par2[j][i] = par2[j-1][par2[j-1][i]];
if(par3[j-1][i] != 0) par3[j][i] = par3[j-1][par3[j-1][i]];
}
}
for(int i=0;i<q;i++){
int s, e, l, r;
s = S[i]+1, e = E[i]+1, l = L[i]+1, r = R[i]+1;
for(int j=18;j>=0;j--){
if(par2[j][s] != 0 && par2[j][s] >= l) s = par2[j][s];
if(par3[j][e] != 0 && par3[j][e] <= r) e = par3[j][e];
}
int ll = s2[s], rr = e2[s];
cur[e].push_back(pipii(i, pii(ll, rr)));
}
dfs(n, 0);
return ans;
}
Compilation message
werewolf.cpp: In function 'void dfs2(int, int)':
werewolf.cpp:27:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g2[u].size();i++){
~^~~~~~~~~~~~~
werewolf.cpp: In function 'void dfs3(int, int)':
werewolf.cpp:37:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g3[u].size();i++){
~^~~~~~~~~~~~~
werewolf.cpp: In function 'void dfs(int, int)':
werewolf.cpp:50:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g3[u].size();i++){
~^~~~~~~~~~~~~
werewolf.cpp:56:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<cur[u].size();i++){
~^~~~~~~~~~~~~~
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:78:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<g[i].size();j++){
~^~~~~~~~~~~~
werewolf.cpp:91:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<g[i].size();j++){
~^~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
28672 KB |
Output is correct |
2 |
Correct |
25 ms |
28672 KB |
Output is correct |
3 |
Correct |
25 ms |
28672 KB |
Output is correct |
4 |
Correct |
25 ms |
28672 KB |
Output is correct |
5 |
Correct |
25 ms |
28644 KB |
Output is correct |
6 |
Correct |
26 ms |
28672 KB |
Output is correct |
7 |
Correct |
25 ms |
28672 KB |
Output is correct |
8 |
Correct |
25 ms |
28672 KB |
Output is correct |
9 |
Correct |
26 ms |
28672 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
28672 KB |
Output is correct |
2 |
Correct |
25 ms |
28672 KB |
Output is correct |
3 |
Correct |
25 ms |
28672 KB |
Output is correct |
4 |
Correct |
25 ms |
28672 KB |
Output is correct |
5 |
Correct |
25 ms |
28644 KB |
Output is correct |
6 |
Correct |
26 ms |
28672 KB |
Output is correct |
7 |
Correct |
25 ms |
28672 KB |
Output is correct |
8 |
Correct |
25 ms |
28672 KB |
Output is correct |
9 |
Correct |
26 ms |
28672 KB |
Output is correct |
10 |
Correct |
32 ms |
30052 KB |
Output is correct |
11 |
Correct |
32 ms |
29916 KB |
Output is correct |
12 |
Correct |
33 ms |
30072 KB |
Output is correct |
13 |
Correct |
32 ms |
30072 KB |
Output is correct |
14 |
Correct |
32 ms |
30072 KB |
Output is correct |
15 |
Correct |
33 ms |
30200 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1077 ms |
147592 KB |
Output is correct |
2 |
Correct |
1008 ms |
122496 KB |
Output is correct |
3 |
Correct |
980 ms |
119196 KB |
Output is correct |
4 |
Correct |
903 ms |
120696 KB |
Output is correct |
5 |
Correct |
873 ms |
121432 KB |
Output is correct |
6 |
Correct |
937 ms |
126948 KB |
Output is correct |
7 |
Correct |
953 ms |
145648 KB |
Output is correct |
8 |
Correct |
879 ms |
122488 KB |
Output is correct |
9 |
Correct |
695 ms |
119288 KB |
Output is correct |
10 |
Correct |
613 ms |
120184 KB |
Output is correct |
11 |
Correct |
702 ms |
121472 KB |
Output is correct |
12 |
Correct |
742 ms |
127272 KB |
Output is correct |
13 |
Correct |
1078 ms |
131320 KB |
Output is correct |
14 |
Correct |
1057 ms |
131320 KB |
Output is correct |
15 |
Correct |
1060 ms |
131308 KB |
Output is correct |
16 |
Correct |
1076 ms |
131320 KB |
Output is correct |
17 |
Correct |
982 ms |
144868 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
28672 KB |
Output is correct |
2 |
Correct |
25 ms |
28672 KB |
Output is correct |
3 |
Correct |
25 ms |
28672 KB |
Output is correct |
4 |
Correct |
25 ms |
28672 KB |
Output is correct |
5 |
Correct |
25 ms |
28644 KB |
Output is correct |
6 |
Correct |
26 ms |
28672 KB |
Output is correct |
7 |
Correct |
25 ms |
28672 KB |
Output is correct |
8 |
Correct |
25 ms |
28672 KB |
Output is correct |
9 |
Correct |
26 ms |
28672 KB |
Output is correct |
10 |
Correct |
32 ms |
30052 KB |
Output is correct |
11 |
Correct |
32 ms |
29916 KB |
Output is correct |
12 |
Correct |
33 ms |
30072 KB |
Output is correct |
13 |
Correct |
32 ms |
30072 KB |
Output is correct |
14 |
Correct |
32 ms |
30072 KB |
Output is correct |
15 |
Correct |
33 ms |
30200 KB |
Output is correct |
16 |
Correct |
1077 ms |
147592 KB |
Output is correct |
17 |
Correct |
1008 ms |
122496 KB |
Output is correct |
18 |
Correct |
980 ms |
119196 KB |
Output is correct |
19 |
Correct |
903 ms |
120696 KB |
Output is correct |
20 |
Correct |
873 ms |
121432 KB |
Output is correct |
21 |
Correct |
937 ms |
126948 KB |
Output is correct |
22 |
Correct |
953 ms |
145648 KB |
Output is correct |
23 |
Correct |
879 ms |
122488 KB |
Output is correct |
24 |
Correct |
695 ms |
119288 KB |
Output is correct |
25 |
Correct |
613 ms |
120184 KB |
Output is correct |
26 |
Correct |
702 ms |
121472 KB |
Output is correct |
27 |
Correct |
742 ms |
127272 KB |
Output is correct |
28 |
Correct |
1078 ms |
131320 KB |
Output is correct |
29 |
Correct |
1057 ms |
131320 KB |
Output is correct |
30 |
Correct |
1060 ms |
131308 KB |
Output is correct |
31 |
Correct |
1076 ms |
131320 KB |
Output is correct |
32 |
Correct |
982 ms |
144868 KB |
Output is correct |
33 |
Correct |
1261 ms |
129148 KB |
Output is correct |
34 |
Correct |
305 ms |
64068 KB |
Output is correct |
35 |
Correct |
1390 ms |
132500 KB |
Output is correct |
36 |
Correct |
1322 ms |
136952 KB |
Output is correct |
37 |
Correct |
1362 ms |
132216 KB |
Output is correct |
38 |
Correct |
1342 ms |
135928 KB |
Output is correct |
39 |
Correct |
1174 ms |
136056 KB |
Output is correct |
40 |
Correct |
1039 ms |
139692 KB |
Output is correct |
41 |
Correct |
953 ms |
131448 KB |
Output is correct |
42 |
Correct |
768 ms |
135468 KB |
Output is correct |
43 |
Correct |
1374 ms |
138756 KB |
Output is correct |
44 |
Correct |
1184 ms |
131896 KB |
Output is correct |
45 |
Correct |
933 ms |
139000 KB |
Output is correct |
46 |
Correct |
954 ms |
135576 KB |
Output is correct |
47 |
Correct |
1096 ms |
137208 KB |
Output is correct |
48 |
Correct |
1068 ms |
137208 KB |
Output is correct |
49 |
Correct |
1069 ms |
137336 KB |
Output is correct |
50 |
Correct |
1061 ms |
137120 KB |
Output is correct |
51 |
Correct |
930 ms |
139256 KB |
Output is correct |
52 |
Correct |
1014 ms |
139388 KB |
Output is correct |