Submission #602365

#	Time	Username	Problem	Language	Result	Execution time	Memory
602365		jairRS	Werewolf (IOI18_werewolf)	C++17	15 / 100	4059 ms	29320 KiB

werewolf

#include "werewolf.h"
#include "bits/stdc++.h"
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;

vvi adj;

void dfsHuman(int src, vector<bool> &reachable, int L)
{
	if (src < L)
		return;
	reachable[src] = true;

	for (int a : adj[src])
	{
		if (reachable[a])
			continue;
		dfsHuman(a, reachable, L);
	}
}

void dfsWolf(int src, vector<bool> &reachable, int R)
{
	if (src > R)
		return;
	reachable[src] = true;

	for (int a : adj[src])
	{
		if (reachable[a])
			continue;
		dfsWolf(a, reachable, R);
	}
}

vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R)
{
	adj = vvi(N);
	for (int i = 0; i < X.size(); i++)
	{
		adj[X[i]].push_back(Y[i]);
		adj[Y[i]].push_back(X[i]);
	}

	auto printVec = [](vector<bool> &vec)
	{
		for (bool x : vec)
			cout << x << " ";
		cout << endl;
	};

	int Q = S.size();
	vi ans(Q, false);
	for (int i = 0; i < Q; i++)
	{
		// cout << "Query ID: " << i << '\n';

		vector<bool> reachableHuman(N, false);
		dfsHuman(S[i], reachableHuman, L[i]);
		// printVec(reachableHuman);

		vector<bool> reachableWolf(N, false);
		dfsWolf(E[i], reachableWolf, R[i]);
		// printVec(reachableWolf);

		for (int a = L[i]; a <= R[i]; a++)
			ans[i] |= (reachableHuman[a] && reachableWolf[a]);
	}

	return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:41:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for (int i = 0; i < X.size(); i++)
      |                  ~~^~~~~~~~~~
werewolf.cpp:47:7: warning: variable 'printVec' set but not used [-Wunused-but-set-variable]
   47 |  auto printVec = [](vector<bool> &vec)
      |       ^~~~~~~~

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