oj.uz

Submission #430728

# Submission time Handle Problem Language Result Execution time Memory
430728 2021-06-17T02:54:03 Z albertolg101 Werewolf (IOI18_werewolf) C++17
0 / 100
 4000 ms 70348 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 204 KB Output is correct
2 Incorrect 3 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 204 KB Output is correct
2 Incorrect 3 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4091 ms 70348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 204 KB Output is correct
2 Incorrect 3 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -