Submission #278728

#	Time	Username	Problem	Language	Result	Execution time	Memory
278728		jairRS	Werewolf (IOI18_werewolf)	C++17	0 / 100	2059 ms	524292 KiB

werewolf

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

set<int> adj[200000];
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)
{
	int Q = S.size();
	int M = X.size();
	for (int i = 0; i < M; i++)
	{
		adj[X[i]].insert(Y[i]);
		adj[Y[i]].insert(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:13:11: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   13 |  if (form == 0 & curcity < l)
      |      ~~~~~^~~~
werewolf.cpp:15:11: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   15 |  if (form == 1 & curcity > r)
      |      ~~~~~^~~~

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