Submission #312716

#	Time	Username	Problem	Language	Result	Execution time	Memory
312716		reymontada61	Werewolf (IOI18_werewolf)	C++14	15 / 100	4070 ms	29968 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

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();
  vector<int> A;
  vector<int> adj[N+1];
  
  int M = X.size();
  
  for (int i=0; i<M; i++) {
	  adj[X[i]].push_back(Y[i]);
	  adj[Y[i]].push_back(X[i]);
  }
  
  bool reach[N+1][2];
  
  for (int i=0; i<Q; i++) {
	  
	  int s = S[i], e = E[i], l = L[i], r = R[i];
	  
	  memset(reach, 0, sizeof reach);
	  queue<pair<int, int>> proc;
	  
	  if (s >= l) proc.push({s, 0});
	  
	  while (!proc.empty()) {
		  
		  auto x = proc.front();
		  proc.pop();
		  
		  int no = x.first;
		  int st = x.second;
		  
		  if (l <= no && no <= r && st == 0) {
			  if (!reach[no][1]) {
				  reach[no][1] = true;
				  proc.push({no, 1});
			  }
		  }
		  
		  for (auto x: adj[no]) {
			  if (st == 0 && x < l) {
				  continue;
			  }
			  else if (st == 1 && x > r) {
				  continue;
			  }
			  else {
				  if (!reach[x][st]) {
					  reach[x][st] = true;
					  proc.push({x, st});
				  }
			  }
		  }
		  
	  }
	  
	  if (reach[e][1]) {
		  A.push_back(1);
	  }
	  else {
		  A.push_back(0);
	  }
  }
  
  return A;
}

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