Submission #142782

#	Time	Username	Problem	Language	Result	Execution time	Memory
142782		cfalas	Werewolf (IOI18_werewolf)	C++14	0 / 100	4027 ms	30068 KiB

werewolf

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

bool dfsWolf(int s, int e, int b, int par=-1){
	if(s>b) return false;
	vis[s] = true;
	if(s==e) return true;
	for(int i=0;i<adj[s].size();i++) if(!vis[adj[s][i]] && adj[s][i]<=b && dfsWolf(adj[s][i], e, b, s)) return true;
	vis[s] = false;
	return false;
}
bool dfsHuman(int s, int e, int b, int par=-1){
	if(s<b) return false;
	vis[s] = true;
	if(s==e) return true;
	for(int i=0;i<adj[s].size();i++) if(!vis[adj[s][i]] && adj[s][i]>=b && dfsHuman(adj[s][i], e, b, s)) return true;
	vis[s] = false;
	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) {
		found = false;
		for(int j=L[i];j<=R[i];j++){
			vis.assign(N+1, false);
			if(dfsHuman(S[i], j, L[i]) && dfsWolf(j, E[i], R[i])){
				found = true;
				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:12:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[s].size();i++) if(!vis[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(!vis[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:29:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<X.size();i++){
              ~^~~~~~~~~

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