Submission #1042972

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042972		thatsgonzalez	Werewolf (IOI18_werewolf)	C++14	0 / 100	4075 ms	51712 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

const int nmax = 3e3+10;

vector<vector<int>> g;
bool res = false;
int n;

void dfs(int node, int endpoint, int l, int r, bool estado, bitset <nmax> vis){

  if(!estado and node<l) {
    return;
  }
  if(estado and node>r) return;
  if(node == endpoint and estado){
    res = true; return;
  }

  vis[node] = 1;

  for(auto &x: g[node]){
    if(vis[x]) continue;

    if(x>=l and x<=r and !estado){
      dfs(x,endpoint,l,r,estado,vis);
      bitset<nmax> nvis;
      dfs(x,endpoint,l,r,!estado,nvis);
    }
    else{
      dfs(x,endpoint,l,r,estado,vis);
    }

  }

}

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
  int Q = S.size();
  int M = X.size();
  std::vector<int> ans(Q,0);
  n = N;
  g.resize(N);
  
  for(int i = 0; i<M; i++){

    g[X[i]].push_back(Y[i]);
    g[Y[i]].push_back(X[i]);

  }

  for(int q = 0; q<Q; q++){

    res = false;
    bitset<nmax> vis;
    dfs(S[q],E[q],L[q],R[q],0,vis);

    ans[q] = res;

    vis.reset();

  }


  return ans;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51