제출 #1015141

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1015141		nisanduu	늑대인간 (IOI18_werewolf)	C++17	0 / 100	4098 ms	32204 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>&vis,ll L,ll R,ll node,ll D,bool isHuman){
    vis[node]=1;
    for(auto el:adj[node]){
        if(!vis[el]){
            if(el==D){
                if(!isHuman) return true;
                if(node <= R) return true;
            }
            else if(isHuman){
                if(el<L){
                    if(node<=R&&dfs1(arr,adj,vis,L,R,el,D,0)) return true;
                }else{
                    if(dfs1(arr,adj,vis,L,R,el,D,1)) return true;
                }
            }else{
                if(el>R) continue;
                dfs1(arr,adj,vis,L,R,el,D,0);
            }
        }
    }
    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),vis1(N+1);
            bool an = dfs1(arr,adj,vis1,L[i],R[i],S[i],E[i],1);
            if(S[i]<L[i]||E[i]>R[i]) an=0;
            
            if(an){
                ans[i]=1;
            }else{
                ans[i]=0;
            }
        }
        return ans;
}

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