oj.uz

Submission #602357

# Submission time Handle Problem Language Result Execution time Memory
602357 2022-07-23T00:22:19 Z jairRS Werewolf (IOI18_werewolf) C++17
0 / 100
 4000 ms 524288 KB 
#include "werewolf.h"
#include "bits/stdc++.h"
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;

const int INF = 1e9;
vvi adj;

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

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

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

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

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 < N; i++)
	{
		adj[X[i]].push_back(Y[i]);
		adj[Y[i]].push_back(X[i]);
	}

	int Q = S.size();
	vi ans(Q, false);
	for (int i = 0; i < Q; i++)
	{
		vector<bool> reachableHuman(N, false);
		dfsHuman(S[i], reachableHuman, L[i]);
		vector<bool> reachableWolf(N, false);
		dfsWolf(E[i], reachableWolf, R[i]);
		for (int a = L[i]; a <= R[i]; a++)
			ans[i] |= (reachableHuman[a] && reachableWolf[a]);
	}

	return ans;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 289 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 289 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 289 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -