oj.uz

답안 #434602

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
434602 2021-06-21T12:51:21 Z Azimjon 늑대인간 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -