# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1015105 | nisanduu | Werewolf (IOI18_werewolf) | C++17 | 0 ms | 0 KiB |
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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
// 1 - Wolf
// 0 - Human
bool f=0;
void dfs1(vector<ll>&arr,vector<vector<ll>>&adj,vector<ll>&vis,ll L,ll R,ll node,ll D){
if(node>L&&node!=D) arr[node]=1;
for(auto el:adj[node]){
if(!vis[el]){
vis[el]=1;
dfs1(arr,adj,vis,L,R,el,D);
}
}
}
void dfs2(vector<ll>&arr,vector<vector<ll>>&adj,vector<ll>&vis,ll L,ll R,ll node,ll E){
if(node<R&&node!=E) {
if(arr[node]==1){
f=1;
return;
}
}
for(auto el:adj[node]){
if(!vis[el]){
vis[el]=1;
dfs2(arr,adj,vis,L,R,el,E);
}
}
}
int[]check_validity(int N, int[] X, int[] Y, int[] S, int[] E, int[]
L, int[] R){
vector<vector<ll>> adj(N+1);
ll M = X.size();
for(ll i=0;i<M;i++){
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
ll Q = S.size();
int ans[Q];
for(ll i=0;i<Q;i++){
vector<ll> arr(N+1,-1),vis1(N+1),vis2(N+1);
f=0;
dfs1(arr,adj,vis1,L[i],R[i],S[i],E[i]);
dfs2(arr,adj,vis2,L[i],R[i],E[i],S[i]);
vis1[S[i]]=1;
vis2[E[i]]=1;
if(f){
ans[i]=1;
}else{
ans[i]=0;
}
}
return ans;
}