This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 num){//quiero que me devuelva una posicion
int L=2*nodo+1,R=L+1,mid=(b+e)/2;
if(b==e){
if(v[b]>=num)return b;
return 0;
}
if(b>=izq && e<=der){
if(T[R].F>=num)return e;
return menor(L,b,mid,izq,der,num);
}
if(der<=mid)return menor(L,b,mid,izq,der,num);
if(izq>mid)return menor(R,mid+1,e,izq,der,num);
return max(menor(L,b,mid,izq,der,num),menor(R,mid+1,e,izq,der,num));
}
int mayor(int nodo, int b, int e, int izq, int der, int num){
int L=2*nodo+1,R=L+1,mid=(b+e)/2;
if(b==e){
return b;
}
if(b>=izq && e<=der){
if(T[R].S<=num)return e;
mayor(L,b,mid,izq,der,num);
}
if(der<=mid)return mayor(L,b,mid,izq,der,num);
if(izq>mid)return mayor(R,mid+1,e,izq,der,num);
return max(mayor(L,b,mid,izq,der,num),mayor(R,mid+1,izq,e,der,num));
}
int menorl(int nodo, int b, int e, int izq, int der, int num){
int L=2*nodo+1,R=L+1,mid=(b+e)/2;
if(b==e){
if(v[b]>=num){
return b;
}
return 200000;
}
if(b>=izq && e<=der){
if(T[L].F>=num)return b;
return menorl(R,mid+1,e,izq,der,num);
}
if(der<=mid)return menorl(L,b,mid,izq,der,num);
if(izq>=mid+1)return menorl(R,mid+1,e,izq,der,num);
return min(menorl(R,mid+1,e,izq,der,num),menorl(L,b,mid,izq,der,num));
}
int mayorl(int nodo, int b, int e, int izq, int der, int num){
int L=2*nodo+1,R=L+1,mid=(b+e)/2;
if(b==e){
if(v[b]<=num)return b;
return 200000;
}
if(b>=izq && e<=der){
if(T[L].S<=num)return b;
return mayorl(L,b,mid,izq,der,num);
}
if(der<=mid)return mayorl(L,b,mid,izq,der,num);
if(izq>=mid+1)return mayorl(R,mid+1,e,izq,der,num);
return min(mayorl(L,b,mid,izq,der,num),mayorl(R,mid+1,e,izq,der,num));
}
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=menorl(0,0,n-1,pos[S[i]],n-1,L[i]);
A2=menor(0,0,n-1,pos[S[i]],n-1,L[i]);
B1=mayorl(0,0,n-1,pos[S[i]],n-1,R[i]);
B2=mayor(0,0,n-1,pos[S[i]],n-1,R[i]);
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 (stderr)
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:105:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for(int i=0;i<X.size();i++){
| ~^~~~~~~~~
werewolf.cpp:117:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
117 | for(int i=0;i<S.size();i++){
| ~^~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |