Submission #143047

#	Time	Username	Problem	Language	Result	Execution time	Memory
143047		cfalas	Werewolf (IOI18_werewolf)	C++14	15 / 100	4037 ms	32088 KiB

werewolf

#include<bits/stdc++.h>
using namespace std;
#include "werewolf.h"
typedef vector<int> vi;
vector<vi> adj;
vector<bool> visWolf;
vector<bool> visHuman;

bool dfsWolf(int s, int e, int b, int par=-1){
	if(s>b) return false;
	visWolf[s] = true;
	if(s==e) return true;
	for(int i=0;i<adj[s].size();i++) if(!visWolf[adj[s][i]] && adj[s][i]<=b && dfsWolf(adj[s][i], e, b, s)) return true;
	return false;
}
bool dfsHuman(int s, int e, int b, int par=-1){
	if(s<b) return false;
	visHuman[s] = true;
	if(s==e) return true;
	for(int i=0;i<adj[s].size();i++) if(!visHuman[adj[s][i]] && adj[s][i]>=b && dfsHuman(adj[s][i], e, b, s)) return true;
	return false;
}

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) {
	adj.assign(N+1, vi());
	for(int i=0;i<X.size();i++){
		adj[X[i]].push_back(Y[i]);
		adj[Y[i]].push_back(X[i]);
	}
	int Q = S.size();
	std::vector<int> A(Q);
	bool found = false;
	for (int i = 0; i < Q; ++i) {
		visWolf.assign(N+1, false);
		visHuman.assign(N+1, false);
		dfsHuman(S[i], -1, L[i]);
		dfsWolf(E[i], -1, R[i]);
		bool found = false;
		for(int j=0;j<N;j++) if(visWolf[j] && visHuman[j]){
			found = 1;
			break;
		}
		if(!found) A[i] = 0;
		else A[i]=1;
	}
	return A;
}

Compilation message (stderr)

werewolf.cpp: In function 'bool dfsWolf(int, int, int, int)':
werewolf.cpp:13:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[s].size();i++) if(!visWolf[adj[s][i]] && adj[s][i]<=b && dfsWolf(adj[s][i], e, b, s)) return true;
              ~^~~~~~~~~~~~~~
werewolf.cpp: In function 'bool dfsHuman(int, int, int, int)':
werewolf.cpp:20:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[s].size();i++) if(!visHuman[adj[s][i]] && adj[s][i]>=b && dfsHuman(adj[s][i], e, b, s)) return true;
              ~^~~~~~~~~~~~~~
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:28:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<X.size();i++){
              ~^~~~~~~~~
werewolf.cpp:34:7: warning: unused variable 'found' [-Wunused-variable]
  bool found = false;
       ^~~~~

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