oj.uz

Submission #434602

# Submission time Handle Problem Language Result Execution time Memory
434602 2021-06-21T12:51:21 Z Azimjon Werewolf (IOI18_werewolf) C++17
15 / 100
 346 ms 21196 KB 
#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 3003;

vector<int> g[N];

int query(int u, int v, int l, int r) {
	vector<int> used(N, 0), used2(N, 0);

	function<void(int)> dfsh = [&](int x) {
		used[x] = 1;
		for (int e : g[x]) {
			if (!used[e] && e >= l) dfsh(e);
		}
	};

	function<void(int)> dfsw = [&](int x) {
		used2[x] = 1;
		for (int e : g[x]) {
			if (!used2[e] && e <= r) dfsw(e);
		}
	};

	dfsh(u);

	dfsw(v);

	for (int i = 0; i < N; i++) {
		if (used[i] && used2[i]) return 1;
	}

	return 0;
}

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();
	std::vector<int> A(Q);

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

	for (int i = 0; i < Q; i++) {
		A[i] = query(S[i], E[i], L[i], R[i]);
	}

	return A;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 313 ms 756 KB Output is correct
11 Correct 174 ms 728 KB Output is correct
12 Correct 24 ms 920 KB Output is correct
13 Correct 346 ms 768 KB Output is correct
14 Correct 231 ms 716 KB Output is correct
15 Correct 281 ms 908 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 166 ms 21196 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 313 ms 756 KB Output is correct
11 Correct 174 ms 728 KB Output is correct
12 Correct 24 ms 920 KB Output is correct
13 Correct 346 ms 768 KB Output is correct
14 Correct 231 ms 716 KB Output is correct
15 Correct 281 ms 908 KB Output is correct
16 Runtime error 166 ms 21196 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -