oj.uz

답안 #1015182

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1015182 2024-07-06T07:04:41 Z nisanduu 늑대인간 (IOI18_werewolf) C++14
0 / 100
 4000 ms 30280 KB 
#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){
            if(!isHuman) return true;
            if(node <= R) 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);
            ans[i]=an;
        }
        return ans;
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4083 ms 30280 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -