oj.uz

Submission #1015131

# Submission time Handle Problem Language Result Execution time Memory
1015131 2024-07-06T06:33:02 Z nisanduu Werewolf (IOI18_werewolf) C++17
0 / 100
 4000 ms 45180 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>&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,1);
            }
        }
    }
    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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4053 ms 45180 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -