oj.uz

Submission #1015207

# Submission time Handle Problem Language Result Execution time Memory
1015207 2024-07-06T07:32:14 Z nisanduu Werewolf (IOI18_werewolf) C++14
0 / 100
 4000 ms 38188 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){
            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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 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 344 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 4062 ms 38188 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 344 KB Output isn't correct
2 Halted 0 ms 0 KB -