Submission #430728

#	Time	Username	Problem	Language	Result	Execution time	Memory
430728		albertolg101	Werewolf (IOI18_werewolf)	C++17	0 / 100	4091 ms	70348 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"

using namespace std;
using pii = pair<int, int>;

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 = L.size(), m = X.size();
	vector<int> ans;
	vector<vector<int>> g(n);

	for(int i = 0 ; i < m ; i++)
	{
		g[X[i]].push_back(Y[i]);
		g[Y[i]].push_back(X[i]);
	}

	vector<vector<int>> dp;
	vector<vector<bool>> flag;

	function<bool(int, int, int, int, int)> dfs = [&](int nod, bool race, int target, int l, int r)
	{
		if(flag[nod][race])
			return dp[nod][race];

		flag[nod][race] = true;
		if(!race and l <= nod and nod <= r)
			dp[nod][race] = dfs(nod, true, target, l, r);

		if(nod == target)
			return dp[nod][race] = race;

		for(auto i: g[nod])
		{
			if(!race and l <= i)
				dp[nod][race] |= dfs(i, race, target, l, r); 
			
			if(race and i <= r)
				dp[nod][race] |= dfs(i, race, target, l, r);
		}

		return dp[nod][race];
	};

	for(int i = 0 ; i < Q ; i++)
	{
		dp = vector<vector<int>> (n, vector<int> (2, 0));
		flag = vector<vector<bool>> (n, vector<bool> (2, false));
		ans.push_back(dfs(S[i], false, E[i], L[i], R[i]));
	}

	return ans;	
}

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