#include "werewolf.h"
#include<bits/stdc++.h>
#define lcm(a,b) (a/__gcd(a,b))*b
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define F first
#define S second
#define mp make_pair
using namespace std;
const int MA=200000;
vector<vi>G;
vi res,v;
int pos[MA];
int cant[MA]={0};
pair<int,int>T[4*MA];
int A1,A2,B1,B2;
void dfs(int nodo, int ant, int p){
pos[nodo]=p;
v.pb(nodo);
for(auto it : G[nodo]){
if(it!=ant){
dfs(it,nodo,p+1);
}
}
}
void init(int nodo, int b, int e){
int L=2*nodo+1,R=L+1,mid=(b+e)/2;
if(b==e){
T[nodo]={v[b],v[e]};
return;
}
init(L,b,mid);init(R,mid+1,e);
T[nodo].F=min(T[L].F,T[R].F);
T[nodo].S=max(T[L].S,T[R].S);
}
int menor(int nodo, int b, int e, int izq, int der){
int L=2*nodo+1,R=L+1,mid=(b+e)/2;
if(b>=izq && der<=e){
return T[nodo].F;
}
if(der<=mid){
return menor(L,b,mid,izq,der);
}
if(izq>=mid+1){
return menor(R,mid+1,e,izq,der);
}
return min(menor(L,b,mid,izq,der),menor(R,mid+1,e,izq,der));
}
int mayor(int nodo, int b, int e, int izq, int der){
int L=2*nodo+1,R=L+1,mid=(b+e)/2;
if(b>=izq && der<=e){
return T[nodo].S;
}
if(der<=mid){
return mayor(L,b,mid,izq,der);
}
if(mid+1<=izq){
return mayor(R,mid+1,e,izq,der);
}
return max(mayor(L,b,mid,izq,der),mayor(R,mid+1,e,izq,der));
}
vi check_validity(int N,vi X,vi Y,vi S,vi E,vi L,vi R) {
//N number of cities
//X ^ Y roads
//S ^ E start and end
//avoid 0,1...L-1 in human form
//avoid R+1,R+2...N-1 in wolf form
int n=N;
G.assign(n+1,vi());
for(int i=0;i<X.size();i++){
G[X[i]].pb(Y[i]);
G[Y[i]].pb(X[i]);
cant[X[i]]++;cant[Y[i]]++;
}
for(int i=0;i<n;i++){
if(cant[i]==1){
dfs(i,-1,0);
break;
}
}
init(0,0,n-1);
for(int i=0;i<S.size();i++){
if(S[i]<L[i] or E[i]>R[i]){
res.pb(0);continue;
}
A1=pos[S[i]],A2=pos[S[i]],B1=pos[E[i]],B2=pos[E[i]];
int b=pos[S[i]],e=n-1;
while(b<=e){
int mid=(b+e)/2;
int mi=menor(0,0,n-1,pos[S[i]],mid);
if(mi<L[i]){
e=mid-1;
}else{
A2=mid;
b=mid+1;
}
}
b=0,e=pos[S[i]];
while(b<=e){
int mid=(b+e)/2;
int mi=menor(0,0,n-1,mid,pos[S[i]]);
if(mi<L[i]){
b=mid+1;
}else{
A1=mid;
e=mid-1;
}
}
b=pos[E[i]],e=n-1;
while(b<=e){
int mid=(b+e)/2;
int ma=mayor(0,0,n-1,pos[E[i]],mid);
if(ma>R[i]){
e=mid-1;
}else{
B2=mid;
b=mid+1;
}
}
b=0,e=pos[E[i]];
while(b<=e){
int mid=(b+e)/2;
int ma=mayor(0,0,n-1,mid,pos[E[i]]);
if(ma>R[i]){
b=mid+1;
}else{
B1=mid;
e=mid-1;
}
}
if(!(A2<B1 or B2<A1)){
res.pb(1);
}else{
res.pb(0);
}
}
return res;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/
/*
5 4 3
0 1
1 2
2 3
3 4
1 3 2 4
0 3 0 4
3 4 2 2
*/
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:73:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for(int i=0;i<X.size();i++){
| ~^~~~~~~~~
werewolf.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(int i=0;i<S.size();i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
359 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
359 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
577 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
359 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
