oj.uz

Submission #602365

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

vvi adj;

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

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

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

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

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

	auto printVec = [](vector<bool> &vec)
	{
		for (bool x : vec)
			cout << x << " ";
		cout << endl;
	};

	int Q = S.size();
	vi ans(Q, false);
	for (int i = 0; i < Q; i++)
	{
		// cout << "Query ID: " << i << '\n';

		vector<bool> reachableHuman(N, false);
		dfsHuman(S[i], reachableHuman, L[i]);
		// printVec(reachableHuman);

		vector<bool> reachableWolf(N, false);
		dfsWolf(E[i], reachableWolf, R[i]);
		// printVec(reachableWolf);

		for (int a = L[i]; a <= R[i]; a++)
			ans[i] |= (reachableHuman[a] && reachableWolf[a]);
	}

	return ans;
}

Compilation message

werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:41:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for (int i = 0; i < X.size(); i++)
      |                  ~~^~~~~~~~~~
werewolf.cpp:47:7: warning: variable 'printVec' set but not used [-Wunused-but-set-variable]
   47 |  auto printVec = [](vector<bool> &vec)
      |       ^~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 260 ms 736 KB Output is correct
11 Correct 140 ms 700 KB Output is correct
12 Correct 16 ms 844 KB Output is correct
13 Correct 278 ms 732 KB Output is correct
14 Correct 177 ms 704 KB Output is correct
15 Correct 281 ms 896 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 260 ms 736 KB Output is correct
11 Correct 140 ms 700 KB Output is correct
12 Correct 16 ms 844 KB Output is correct
13 Correct 278 ms 732 KB Output is correct
14 Correct 177 ms 704 KB Output is correct
15 Correct 281 ms 896 KB Output is correct
16 Execution timed out 4059 ms 29320 KB Time limit exceeded
17 Halted 0 ms 0 KB -