#include "werewolf.h"
#include <vector>
#include <algorithm>
#include <deque>
#include <iostream>
using namespace std;
#define MAX_N 200000
vector<int> gp[MAX_N+1];
vector<int> ans;
struct ST{
int s, e;
int l, r;
vector<int> v;
};
vector<ST> MST;
vector<int> ex;
int Lp[MAX_N+1][20], Rp[MAX_N+1][20];
int Lg[MAX_N+1], Rg[MAX_N+1];
int fLg(int x){
if(x==Lg[x]) return x;
return Lg[x]=fLg(Lg[x]);
}
int fRg(int x){
if(x==Rg[x]) return x;
return Rg[x]=fRg(Rg[x]);
}
int n, m, q;
vector<int> lgp[MAX_N+1], rgp[MAX_N+1];
int lidx[MAX_N+1][2], ridx[MAX_N+1][2];
int idx=0;
void ldfs(int x){
lidx[x][0]=++idx;
for(int i=0; i<lgp[x].size(); i++){
ldfs(lgp[x][i]);
}
lidx[x][1]=idx;
}
void rdfs(int x){
ridx[x][0]=++idx;
for(int i=0; i<rgp[x].size(); i++){
rdfs(rgp[x][i]);
}
ridx[x][1]=idx;
}
int arr[MAX_N+1];
deque<int> dq;
void init(){
int x=0;
dq.push_back(0);
while(!dq.empty()){
x=dq.front(); dq.pop_front();
if(MST[x].s!=MST[x].e){
if(MST[x].l==-1){
MST[x].l=(int)MST.size();
MST.push_back({MST[x].s, (MST[x].s+MST[x].e)/2, -1, -1, ex});
dq.push_back(MST[x].l);
}
if(MST[x].r==-1){
MST[x].r=(int)MST.size();
MST.push_back({(MST[x].s+MST[x].e)/2+1, MST[x].e, -1, -1, ex});
dq.push_back(MST[x].r);
}
}else {MST[x].v.push_back(arr[MST[x].s]);}
}
dq.clear();
int i1=0, i2=0;
x=(int)MST.size()-1;
while(1){
if(MST[x].s!=MST[x].e){
i1=i2=0;
//MST[x].v.resize(MST[MST[x].l].v.size()+MST[MST[x].r].v.size());
while(1){
if(i1==MST[MST[x].l].v.size() && i2==MST[MST[x].r].v.size()) break;
if(i1==MST[MST[x].l].v.size()){
MST[x].v.push_back(MST[MST[x].r].v[i2++]);
}else if(i2==MST[MST[x].r].v.size()){
MST[x].v.push_back(MST[MST[x].l].v[i1++]);
}else{
if(MST[MST[x].l].v[i1]<MST[MST[x].r].v[i2]){
MST[x].v.push_back(MST[MST[x].l].v[i1++]);
}else{
MST[x].v.push_back(MST[MST[x].r].v[i2++]);
}
}
}
}
if(x==0) return;
x--;
}
}
ST now;
vector<int>::iterator it;
bool check(int idx, int x, int y, int z, int w){
if(MST[idx].s>y || MST[idx].e<x) return false;
if(x<=MST[idx].s && MST[idx].e<=y){
it=lower_bound(MST[idx].v.begin(), MST[idx].v.end(), z);
if(it==MST[idx].v.end()) return false;
return (*it<=w);
}
if(check(MST[idx].l, x, y, z, w)) return true;
return check(MST[idx].r, x, y, z, w);
}
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; m=(int)X.size(); q=(int)S.size();
for(int i=0; i<m; i++){
gp[X[i]].push_back(Y[i]); gp[Y[i]].push_back(X[i]);
}
for(int i=0; i<n; i++){
Lg[i]=Rg[i]=i;
Lp[i][0]=0; Rp[i][0]=n-1;
}
for(int i=n-1; i>=0; i--){
for(int j=0; j<gp[i].size(); j++){
if(gp[i][j]>i){
int a=fLg(i), b=fLg(gp[i][j]);
if(a!=b){
Lg[b]=a; Lp[b][0]=a; lgp[a].push_back(b);
}
}
}
}
idx=-1; ldfs(fLg(0));
for(int i=0; i<n; i++){
for(int j=0; j<gp[i].size(); j++){
if(gp[i][j]<i){
int a=fRg(i), b=fRg(gp[i][j]);
if(a!=b){
Rg[b]=a; Rp[b][0]=a; rgp[a].push_back(b);
}
}
}
}
idx=-1; rdfs(fRg(0));
for(int i=1; i<20; i++){
for(int j=0; j<n; j++){
Lp[j][i]=Lp[Lp[j][i-1]][i-1]; Rp[j][i]=Rp[Rp[j][i-1]][i-1];
}
}
for(int i=0; i<n; i++) arr[lidx[i][0]]=ridx[i][0];
MST.push_back({0, N-1, -1, -1, ex});
init();
for(int i=0; i<q; i++){
int s=S[i], e=E[i], l=L[i], r=R[i];
//cout<<s<<" "<<e<<" "<<l<<" "<<r<<endl;
for(int i=19; i>=0; i--){
if(l<=Lp[s][i]) s=Lp[s][i];
if(Rp[e][i]<=r) e=Rp[e][i];
}
//cout<<s<<" "<<e<<" "<<l<<" "<<r<<endl;
if(check(0, lidx[s][0], lidx[s][1], ridx[e][0], ridx[e][1])){
ans.push_back(1);
}else ans.push_back(0);
}
return ans;
}
Compilation message
werewolf.cpp: In function 'void ldfs(int)':
werewolf.cpp:45:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<lgp[x].size(); i++){
~^~~~~~~~~~~~~~
werewolf.cpp: In function 'void rdfs(int)':
werewolf.cpp:53:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<rgp[x].size(); i++){
~^~~~~~~~~~~~~~
werewolf.cpp: In function 'void init()':
werewolf.cpp:88:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i1==MST[MST[x].l].v.size() && i2==MST[MST[x].r].v.size()) break;
~~^~~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:88:52: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i1==MST[MST[x].l].v.size() && i2==MST[MST[x].r].v.size()) break;
~~^~~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:89:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i1==MST[MST[x].l].v.size()){
~~^~~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:91:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
}else if(i2==MST[MST[x].r].v.size()){
~~^~~~~~~~~~~~~~~~~~~~~~~~
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:131:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<gp[i].size(); j++){
~^~~~~~~~~~~~~
werewolf.cpp:142:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<gp[i].size(); j++){
~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
14584 KB |
Output is correct |
2 |
Correct |
14 ms |
14584 KB |
Output is correct |
3 |
Correct |
14 ms |
14460 KB |
Output is correct |
4 |
Correct |
13 ms |
14456 KB |
Output is correct |
5 |
Correct |
14 ms |
14584 KB |
Output is correct |
6 |
Correct |
13 ms |
14584 KB |
Output is correct |
7 |
Correct |
14 ms |
14456 KB |
Output is correct |
8 |
Correct |
14 ms |
14456 KB |
Output is correct |
9 |
Correct |
13 ms |
14456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
14584 KB |
Output is correct |
2 |
Correct |
14 ms |
14584 KB |
Output is correct |
3 |
Correct |
14 ms |
14460 KB |
Output is correct |
4 |
Correct |
13 ms |
14456 KB |
Output is correct |
5 |
Correct |
14 ms |
14584 KB |
Output is correct |
6 |
Correct |
13 ms |
14584 KB |
Output is correct |
7 |
Correct |
14 ms |
14456 KB |
Output is correct |
8 |
Correct |
14 ms |
14456 KB |
Output is correct |
9 |
Correct |
13 ms |
14456 KB |
Output is correct |
10 |
Correct |
22 ms |
16056 KB |
Output is correct |
11 |
Correct |
22 ms |
15928 KB |
Output is correct |
12 |
Correct |
22 ms |
15976 KB |
Output is correct |
13 |
Correct |
21 ms |
16184 KB |
Output is correct |
14 |
Correct |
21 ms |
16056 KB |
Output is correct |
15 |
Correct |
23 ms |
16056 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
907 ms |
120444 KB |
Output is correct |
2 |
Correct |
955 ms |
131232 KB |
Output is correct |
3 |
Correct |
886 ms |
129596 KB |
Output is correct |
4 |
Correct |
856 ms |
128972 KB |
Output is correct |
5 |
Correct |
784 ms |
128948 KB |
Output is correct |
6 |
Correct |
1002 ms |
128956 KB |
Output is correct |
7 |
Correct |
966 ms |
128700 KB |
Output is correct |
8 |
Correct |
838 ms |
131260 KB |
Output is correct |
9 |
Correct |
776 ms |
129504 KB |
Output is correct |
10 |
Correct |
741 ms |
129116 KB |
Output is correct |
11 |
Correct |
698 ms |
129084 KB |
Output is correct |
12 |
Correct |
640 ms |
128936 KB |
Output is correct |
13 |
Correct |
1006 ms |
136252 KB |
Output is correct |
14 |
Correct |
985 ms |
135996 KB |
Output is correct |
15 |
Correct |
1010 ms |
136128 KB |
Output is correct |
16 |
Correct |
987 ms |
136152 KB |
Output is correct |
17 |
Correct |
857 ms |
128836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
14584 KB |
Output is correct |
2 |
Correct |
14 ms |
14584 KB |
Output is correct |
3 |
Correct |
14 ms |
14460 KB |
Output is correct |
4 |
Correct |
13 ms |
14456 KB |
Output is correct |
5 |
Correct |
14 ms |
14584 KB |
Output is correct |
6 |
Correct |
13 ms |
14584 KB |
Output is correct |
7 |
Correct |
14 ms |
14456 KB |
Output is correct |
8 |
Correct |
14 ms |
14456 KB |
Output is correct |
9 |
Correct |
13 ms |
14456 KB |
Output is correct |
10 |
Correct |
22 ms |
16056 KB |
Output is correct |
11 |
Correct |
22 ms |
15928 KB |
Output is correct |
12 |
Correct |
22 ms |
15976 KB |
Output is correct |
13 |
Correct |
21 ms |
16184 KB |
Output is correct |
14 |
Correct |
21 ms |
16056 KB |
Output is correct |
15 |
Correct |
23 ms |
16056 KB |
Output is correct |
16 |
Correct |
907 ms |
120444 KB |
Output is correct |
17 |
Correct |
955 ms |
131232 KB |
Output is correct |
18 |
Correct |
886 ms |
129596 KB |
Output is correct |
19 |
Correct |
856 ms |
128972 KB |
Output is correct |
20 |
Correct |
784 ms |
128948 KB |
Output is correct |
21 |
Correct |
1002 ms |
128956 KB |
Output is correct |
22 |
Correct |
966 ms |
128700 KB |
Output is correct |
23 |
Correct |
838 ms |
131260 KB |
Output is correct |
24 |
Correct |
776 ms |
129504 KB |
Output is correct |
25 |
Correct |
741 ms |
129116 KB |
Output is correct |
26 |
Correct |
698 ms |
129084 KB |
Output is correct |
27 |
Correct |
640 ms |
128936 KB |
Output is correct |
28 |
Correct |
1006 ms |
136252 KB |
Output is correct |
29 |
Correct |
985 ms |
135996 KB |
Output is correct |
30 |
Correct |
1010 ms |
136128 KB |
Output is correct |
31 |
Correct |
987 ms |
136152 KB |
Output is correct |
32 |
Correct |
857 ms |
128836 KB |
Output is correct |
33 |
Correct |
1369 ms |
128956 KB |
Output is correct |
34 |
Correct |
304 ms |
46940 KB |
Output is correct |
35 |
Correct |
1339 ms |
131252 KB |
Output is correct |
36 |
Correct |
1286 ms |
129340 KB |
Output is correct |
37 |
Correct |
1343 ms |
130456 KB |
Output is correct |
38 |
Correct |
1254 ms |
129712 KB |
Output is correct |
39 |
Correct |
991 ms |
136444 KB |
Output is correct |
40 |
Correct |
1006 ms |
138940 KB |
Output is correct |
41 |
Correct |
828 ms |
129900 KB |
Output is correct |
42 |
Correct |
755 ms |
129428 KB |
Output is correct |
43 |
Correct |
1156 ms |
136068 KB |
Output is correct |
44 |
Correct |
1178 ms |
130380 KB |
Output is correct |
45 |
Correct |
782 ms |
136764 KB |
Output is correct |
46 |
Correct |
877 ms |
136656 KB |
Output is correct |
47 |
Correct |
1232 ms |
136372 KB |
Output is correct |
48 |
Correct |
1268 ms |
136124 KB |
Output is correct |
49 |
Correct |
1246 ms |
136256 KB |
Output is correct |
50 |
Correct |
1186 ms |
136252 KB |
Output is correct |
51 |
Correct |
1123 ms |
138940 KB |
Output is correct |
52 |
Correct |
1154 ms |
138812 KB |
Output is correct |