Submission #1015207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015207		nisanduu	Werewolf (IOI18_werewolf)	C++14	0 / 100	4062 ms	38188 KiB

werewolf

#include <bits/stdc++.h> 
// #include "werewolf.h"
using namespace std;
typedef long long ll;

// 0 - Wolf
// 1 - Human

bool dfs1(vector<ll>&arr,vector<vector<ll>>&adj,vector<ll>&wolvesVis,vector<ll>&humanVis,ll L,ll R,ll node,ll D,bool isHuman){
    if(isHuman) humanVis[node]=1;
    else wolvesVis[node]=1;
    for(auto el:adj[node]){
        if(el==D){
            return true;
            
        }
        else if(isHuman){
            if(el<L){
                if(node<=R && !wolvesVis[el] && dfs1(arr,adj,wolvesVis,humanVis,L,R,el,D,0)) return true;
            }else{
                if(el>R){
                    if(!humanVis[el] && dfs1(arr,adj,wolvesVis,humanVis,L,R,el,D,1)) return true;
                }else{
                    if(node<=R && !wolvesVis[el] && dfs1(arr,adj,wolvesVis,humanVis,L,R,el,D,0)) return true;
                    if(!humanVis[el] && dfs1(arr,adj,wolvesVis,humanVis,L,R,el,D,1)) return true;
                }
            }
        }else{
            if(el<=R) {
                if(!wolvesVis[el] && dfs1(arr,adj,wolvesVis,humanVis,L,R,el,D,0)) return true;
            }
        }
    }
    return false;
}

vector<int> check_validity(int	N,	vector<int>	X,	vector<int>	Y,	vector<int>	S,	vector<int>	E,	vector<int>
	L,	vector<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();
        vector<int> ans(Q);
        for(ll i=0;i<Q;i++){
            //if(i!=2) continue;
            vector<ll> arr(N+1,-1),wolvesVis(N+1),humanVis(N+1);
            bool an = dfs1(arr,adj,wolvesVis,humanVis,L[i],R[i],S[i],E[i],1);
            if(S[i]<R[i]) an |= dfs1(arr,adj,wolvesVis,humanVis,L[i],R[i],S[i],E[i],0);
            ans[i]=an;
        }
        return ans;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51