oj.uz

Submission #1015261

# Submission time Handle Problem Language Result Execution time Memory
1015261 2024-07-06T08:06:55 Z nisanduu Werewolf (IOI18_werewolf) C++14
0 / 100
 4000 ms 47684 KB 
#include <bits/stdc++.h> 
// #include "werewolf.h"
using namespace std;
typedef int ll;

// 0 - Wolf
// 1 - Human

vector<vector<ll>> adj;
vector<ll> visH, visW;
ll l,r,d;

// bool dfs(ll node,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(el,0)) return true;
//             }else{
//                 if(el>R){
//                     if(!humanVis[el] && dfs1(el,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;
// }

bool dfs(ll node, bool isHuman) {
    if (isHuman && visH[node]) {
        return false;
    } else if (!isHuman && visW[node]) {
        return false;
    } else {
        if (isHuman) {
            visH[node] = true;
        } else {
            visW[node] = true;
        }
    }

    if (node == d) {
        return true;
    }

    if (isHuman && node < l) {
        return false;
    }

    if (!isHuman && node > r) {
        return false;
    }

    if (isHuman == true && l <= node && node <= r) {
        for (auto i: adj[node]) {
            if (dfs(i, false)) return true;
        }
    }

    for (auto i: adj[node]) {
        if (dfs(i, isHuman)) 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>> adjc(N+1);
        ll M = X.size();
        for(ll i=0;i<M;i++){
            adjc[X[i]].push_back(Y[i]);
            adjc[Y[i]].push_back(X[i]);
        }

        adj = adjc;
        
        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;

            l = L[i];
            r = R[i];
            d = E[i];

            vector<int> visited(N+1);
            visW = visited;
            visH = visited;

            ans[i] = (int)dfs(S[i], true);
        }
        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 4049 ms 47684 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 -