#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#define M 200100
typedef vector<int> VI;
struct dsu{
int par[M];
int abp(int n){
return par[n]?par[n]=abp(par[n]):n;
}
int merge(int a,int b){
a++;b++;
a=abp(a),b=abp(b);
if(a-b)par[a]=b;
return a!=b;
}
} dsuhuman,dsuwolf;
int bjh[M][20],bjw[M][20],in[M],out[M],CC;
vector<pair<int,int>>qry[M];
set<int>st[M];
VI EDGES[M],adjh[M],adjw[M];
vector<int>ans;
void dfsw(int n){
in[n]=++CC;
for(auto i:adjw[n])
dfsw(i);
out[n]=CC;
}
void merge(int a,int b){
if(st[a].size()<st[b].size())
swap(st[a],st[b]);
for(auto i:st[b])
st[a].insert(i);
st[b].clear();
}
void dfsans(int n){
st[n].insert(in[n]);
for(auto i:adjh[n])
dfsans(i),merge(n,i);
for(auto[i,x]:qry[n])
ans[i]=st[n].lower_bound(in[x])!=
st[n].upper_bound(out[x]);
}
VI check_validity(int N,VI X,VI Y,VI S,VI E,VI L,VI R) {
for(int i=0;i<X.size();i++)
EDGES[X[i]].push_back(Y[i]),
EDGES[Y[i]].push_back(X[i]);
for(int i=N;i--;)
for(auto k:EDGES[i]) {
if(k<i)continue;
int x=dsuhuman.abp(k+1)-1;
if(x==i) continue;
bjh[x][0]=i,adjh[i].push_back(x);
dsuhuman.merge(x,i);
}
for(int i=0;i<N;i++)
for(auto k:EDGES[i]) {
if(k>i)continue;
int x=dsuwolf.abp(k+1)-1;
if(x==i) continue;
bjw[x][0]=i,adjw[i].push_back(x);
dsuwolf.merge(x,i);
}
bjw[N-1][0]=bjw[N][0]=N;
for(int j=1;j<20;j++)
for(int i=0;i<=N;i++)
bjw[i][j]=bjw[bjw[i][j-1]][j-1],
bjh[i][j]=bjh[bjh[i][j-1]][j-1];
dfsw(N-1);
int Q=S.size();
ans=S;
for(int i=0;i<Q;i++){
int l=L[i],r=R[i],s=S[i],e=E[i];
for(int i=20;i--;)
if(bjh[s][i]>=l)
s=bjh[s][i];
for(int i=20;i--;)
if(bjw[e][i]<=r)
e=bjw[e][i];
qry[s].push_back({i,e});
}
dfsans(0);
return ans;
}
Compilation message
werewolf.cpp: In function 'VI check_validity(int, VI, VI, VI, VI, VI, VI)':
werewolf.cpp:45:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int i=0;i<X.size();i++)
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
29272 KB |
Output is correct |
2 |
Correct |
8 ms |
29308 KB |
Output is correct |
3 |
Correct |
8 ms |
29276 KB |
Output is correct |
4 |
Correct |
8 ms |
29272 KB |
Output is correct |
5 |
Correct |
8 ms |
29316 KB |
Output is correct |
6 |
Correct |
10 ms |
29276 KB |
Output is correct |
7 |
Correct |
11 ms |
29336 KB |
Output is correct |
8 |
Correct |
10 ms |
29276 KB |
Output is correct |
9 |
Correct |
8 ms |
29276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
29272 KB |
Output is correct |
2 |
Correct |
8 ms |
29308 KB |
Output is correct |
3 |
Correct |
8 ms |
29276 KB |
Output is correct |
4 |
Correct |
8 ms |
29272 KB |
Output is correct |
5 |
Correct |
8 ms |
29316 KB |
Output is correct |
6 |
Correct |
10 ms |
29276 KB |
Output is correct |
7 |
Correct |
11 ms |
29336 KB |
Output is correct |
8 |
Correct |
10 ms |
29276 KB |
Output is correct |
9 |
Correct |
8 ms |
29276 KB |
Output is correct |
10 |
Correct |
13 ms |
30556 KB |
Output is correct |
11 |
Correct |
12 ms |
30520 KB |
Output is correct |
12 |
Correct |
12 ms |
30552 KB |
Output is correct |
13 |
Correct |
15 ms |
30668 KB |
Output is correct |
14 |
Correct |
13 ms |
30556 KB |
Output is correct |
15 |
Correct |
12 ms |
30556 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
451 ms |
112468 KB |
Output is correct |
2 |
Correct |
382 ms |
110676 KB |
Output is correct |
3 |
Correct |
457 ms |
109396 KB |
Output is correct |
4 |
Correct |
434 ms |
109008 KB |
Output is correct |
5 |
Correct |
388 ms |
109648 KB |
Output is correct |
6 |
Correct |
402 ms |
111328 KB |
Output is correct |
7 |
Correct |
379 ms |
111708 KB |
Output is correct |
8 |
Correct |
361 ms |
110700 KB |
Output is correct |
9 |
Correct |
364 ms |
108880 KB |
Output is correct |
10 |
Correct |
331 ms |
108784 KB |
Output is correct |
11 |
Correct |
371 ms |
108648 KB |
Output is correct |
12 |
Correct |
338 ms |
109648 KB |
Output is correct |
13 |
Correct |
411 ms |
125776 KB |
Output is correct |
14 |
Correct |
422 ms |
126036 KB |
Output is correct |
15 |
Correct |
391 ms |
125776 KB |
Output is correct |
16 |
Correct |
429 ms |
125780 KB |
Output is correct |
17 |
Correct |
415 ms |
111692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
29272 KB |
Output is correct |
2 |
Correct |
8 ms |
29308 KB |
Output is correct |
3 |
Correct |
8 ms |
29276 KB |
Output is correct |
4 |
Correct |
8 ms |
29272 KB |
Output is correct |
5 |
Correct |
8 ms |
29316 KB |
Output is correct |
6 |
Correct |
10 ms |
29276 KB |
Output is correct |
7 |
Correct |
11 ms |
29336 KB |
Output is correct |
8 |
Correct |
10 ms |
29276 KB |
Output is correct |
9 |
Correct |
8 ms |
29276 KB |
Output is correct |
10 |
Correct |
13 ms |
30556 KB |
Output is correct |
11 |
Correct |
12 ms |
30520 KB |
Output is correct |
12 |
Correct |
12 ms |
30552 KB |
Output is correct |
13 |
Correct |
15 ms |
30668 KB |
Output is correct |
14 |
Correct |
13 ms |
30556 KB |
Output is correct |
15 |
Correct |
12 ms |
30556 KB |
Output is correct |
16 |
Correct |
451 ms |
112468 KB |
Output is correct |
17 |
Correct |
382 ms |
110676 KB |
Output is correct |
18 |
Correct |
457 ms |
109396 KB |
Output is correct |
19 |
Correct |
434 ms |
109008 KB |
Output is correct |
20 |
Correct |
388 ms |
109648 KB |
Output is correct |
21 |
Correct |
402 ms |
111328 KB |
Output is correct |
22 |
Correct |
379 ms |
111708 KB |
Output is correct |
23 |
Correct |
361 ms |
110700 KB |
Output is correct |
24 |
Correct |
364 ms |
108880 KB |
Output is correct |
25 |
Correct |
331 ms |
108784 KB |
Output is correct |
26 |
Correct |
371 ms |
108648 KB |
Output is correct |
27 |
Correct |
338 ms |
109648 KB |
Output is correct |
28 |
Correct |
411 ms |
125776 KB |
Output is correct |
29 |
Correct |
422 ms |
126036 KB |
Output is correct |
30 |
Correct |
391 ms |
125776 KB |
Output is correct |
31 |
Correct |
429 ms |
125780 KB |
Output is correct |
32 |
Correct |
415 ms |
111692 KB |
Output is correct |
33 |
Correct |
456 ms |
110948 KB |
Output is correct |
34 |
Correct |
168 ms |
63568 KB |
Output is correct |
35 |
Correct |
459 ms |
115064 KB |
Output is correct |
36 |
Correct |
422 ms |
111000 KB |
Output is correct |
37 |
Correct |
430 ms |
113732 KB |
Output is correct |
38 |
Correct |
438 ms |
112208 KB |
Output is correct |
39 |
Correct |
419 ms |
116820 KB |
Output is correct |
40 |
Correct |
452 ms |
124616 KB |
Output is correct |
41 |
Correct |
372 ms |
112028 KB |
Output is correct |
42 |
Correct |
365 ms |
109444 KB |
Output is correct |
43 |
Correct |
492 ms |
121000 KB |
Output is correct |
44 |
Correct |
376 ms |
112976 KB |
Output is correct |
45 |
Correct |
403 ms |
115436 KB |
Output is correct |
46 |
Correct |
413 ms |
115048 KB |
Output is correct |
47 |
Correct |
420 ms |
125848 KB |
Output is correct |
48 |
Correct |
384 ms |
125776 KB |
Output is correct |
49 |
Correct |
417 ms |
126036 KB |
Output is correct |
50 |
Correct |
382 ms |
125780 KB |
Output is correct |
51 |
Correct |
475 ms |
124552 KB |
Output is correct |
52 |
Correct |
464 ms |
124304 KB |
Output is correct |