Submission #280481

#	Time	Username	Problem	Language	Result	Execution time	Memory
280481		jairRS	Werewolf (IOI18_werewolf)	C++17	15 / 100	4086 ms	45804 KiB

werewolf

#include "werewolf.h"
#include <set>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;

VVI adj;
int memo[200000][2];

int dp(int curcity, int endcity, int l, int r, vector<bool> &visited, int form = 0)
{
	if (form == 0 & curcity < l)
		return 0;
	if (form == 1 & curcity > r)
		return 0;
	if (curcity == endcity && form == 1)
		return 1;
	if (memo[curcity][form] != -1)
		return memo[curcity][form];

	visited[curcity] = true;

	int res = 0;
	for (int adjcity : adj[curcity])
	{
		if (visited[adjcity])
			continue;
		res += dp(adjcity, endcity, l, r, visited, form);
	}

	if (form != 1)
	{
		vector<bool> nvisited(visited.size());
		res += dp(curcity, endcity, l, r, nvisited, 1);
	}

	memo[curcity][form] = res;
	return res;
}

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 = VVI(N);
	int Q = S.size();
	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]);
	}

	std::vector<int> A(Q);
	for (int i = 0; i < Q; i++)
	{
		vector<bool> nvisited(N);
		memset(memo, -1, sizeof(memo));
		int ans = dp(S[i], E[i], L[i], R[i], nvisited);
		ans = min(ans, 1);
		A[i] = ans;
	}
	return A;
}

Compilation message (stderr)

werewolf.cpp: In function 'int dp(int, int, int, int, std::vector<bool>&, int)':
werewolf.cpp:15:11: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   15 |  if (form == 0 & curcity < l)
      |      ~~~~~^~~~
werewolf.cpp:17:11: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   17 |  if (form == 1 & curcity > r)
      |      ~~~~~^~~~

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