Submission #1015261

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015261		nisanduu	Werewolf (IOI18_werewolf)	C++14	0 / 100	4049 ms	47684 KiB

werewolf

#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
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51