#include "werewolf.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll N,M,K,Q,prosli[200005],pos[200005],pvred,mesto[200005],niz[200005],stmax[525000],stmin[525000];
vector<int> graf[200005],ret;
struct kveri{
int poc,kraj,id;
ll L,R;
} upiti[200005];
void dfs2(int gde,int dub){
prosli[gde]=pvred;
mesto[gde]=dub;
niz[dub]=gde;
for(int i=0;i<graf[gde].size();i++)
if(prosli[graf[gde][i]]!=pvred)
dfs2(graf[gde][i],dub+1);
return;
}
void dfs(int gde,int L,int R){
prosli[gde]=pvred;
pos[gde]++;
for(int i=0;i<graf[gde].size();i++){
if(prosli[graf[gde][i]]==pvred)
continue;
if(graf[gde][i]<L)
continue;
if(graf[gde][i]>R)
continue;
dfs(graf[gde][i],L,R);
}
}
ll getmax(int gde,int lg,int dg,int lc,int dc){
if(lg==lc and dg==dc)
return stmax[gde];
int sred=(lc+dc)/2;
if(dg<=sred)
return getmax(gde*2,lg,dg,lc,sred);
if(lg>sred)
return getmax(gde*2+1,lg,dg,sred+1,dc);
return max(getmax(gde*2,lg,sred,lc,sred),getmax(gde*2+1,sred+1,dg,sred+1,dc));
}
ll getmin(int gde,int lg,int dg,int lc,int dc){
if(lg==lc and dg==dc)
return stmin[gde];
int sred=(lc+dc)/2;
if(dg<=sred)
return getmin(gde*2,lg,dg,lc,sred);
if(lg>sred)
return getmin(gde*2+1,lg,dg,sred+1,dc);
return min(getmin(gde*2,lg,sred,lc,sred),getmin(gde*2+1,sred+1,dg,sred+1,dc));
}
vector<int> check_validity(int NN, vector<int> X, vector<int> Y,vector<int> S, vector<int> E,vector<int> L, vector<int> R) {
N=NN;
M=X.size();
Q=L.size();
ret.resize(Q);
for(int i=0;i<M;i++){
X[i]++;
Y[i]++;
graf[X[i]].push_back(Y[i]);
graf[Y[i]].push_back(X[i]);
}
for(int i=0;i<Q;i++){
S[i]++;
E[i]++;
L[i]++;
R[i]++;
upiti[i+1].id=i;
upiti[i+1].poc=S[i];
upiti[i+1].kraj=E[i];
upiti[i+1].L=L[i];
upiti[i+1].R=R[i];
}
for(int i=1;i<=N;i++)
if(graf[i].size()==1){
dfs2(i,1);
break;
}
K=1;
while(K<N)
K<<=1;
for(int i=1;i<=N;i++)
stmin[i+K-1]=stmax[i+K-1]=niz[i];
for(int i=N+K;i<=K+K;i++)
stmin[i]=1e9;
for(int i=K-1;i>=1;i--){
stmax[i]=max(stmax[i*2],stmax[i*2+1]);
stmin[i]=min(stmin[i*2],stmin[i*2+1]);
}
ll lg,dg,sred,v,m;
/* for(int j=1;j<=Q;j++){
lg=mesto[upiti[j].poc];
dg=mesto[upiti[j].kraj];
if(lg==dg){
ret[upiti[j].id]=1;
continue;
}
if(lg<dg){
while(lg<=dg){
sred=(lg+dg)/2;
v=getmax(1,mesto[upiti[j].poc],sred,1,K);
m=getmin(1,sred,mesto[upiti[j].kraj],1,K);
if(v>=upiti[j].L and m<=upiti[j].R){
ret[upiti[j].id]=1;
break;
}
if(v<upiti[j].L and m>upiti[j].R)
break;
if(v>=upiti[j].L)
lg=sred+1;
else
dg=sred-1;
}
continue;
}
swap(lg,dg);
while(lg<=dg){
sred=(lg+dg)/2;
v=getmax(1,sred,mesto[upiti[j].poc],1,K);
m=getmin(1,mesto[upiti[j].kraj],sred,1,K);
if(v>=upiti[j].L and m<=upiti[j].R){
ret[upiti[j].id]=1;
break;
}
if(v<upiti[j].L and m>upiti[j].R)
break;
if(v>=upiti[j].L)
lg=sred+1;
else
dg=sred-1;
}
}*/
return ret;
}
Compilation message
werewolf.cpp: In function 'void dfs2(int, int)':
werewolf.cpp:15:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | for(int i=0;i<graf[gde].size();i++)
| ~^~~~~~~~~~~~~~~~~
werewolf.cpp: In function 'void dfs(int, int, int)':
werewolf.cpp:23:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for(int i=0;i<graf[gde].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:91:10: warning: unused variable 'lg' [-Wunused-variable]
91 | ll lg,dg,sred,v,m;
| ^~
werewolf.cpp:91:13: warning: unused variable 'dg' [-Wunused-variable]
91 | ll lg,dg,sred,v,m;
| ^~
werewolf.cpp:91:16: warning: unused variable 'sred' [-Wunused-variable]
91 | ll lg,dg,sred,v,m;
| ^~~~
werewolf.cpp:91:21: warning: unused variable 'v' [-Wunused-variable]
91 | ll lg,dg,sred,v,m;
| ^
werewolf.cpp:91:23: warning: unused variable 'm' [-Wunused-variable]
91 | ll lg,dg,sred,v,m;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
194 ms |
36216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
