oj.uz

답안 #962016

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
962016 2024-04-13T03:50:24 Z IBory Tales of seafaring (POI13_mor) C++17
100 / 100
 1121 ms 117968 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int MAX = 5005;
vector<int> G[MAX];
short D[MAX][MAX][2];

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, M, Q;
	cin >> N >> M >> Q;
	for (int i = 1; i <= M; ++i) {
		int a, b;
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}

	memset(D, 0x3f, sizeof(D));
	for (int i = 1; i <= N; ++i) {
		queue<pii> Q;
		Q.emplace(i, 0);
		D[i][i][0] = 0;
		while (!Q.empty()) {
			auto [cur, p] = Q.front(); Q.pop();
			for (int next : G[cur]) {
				int np = p ^ 1;
				if (D[i][next][np] < 11111) continue;
				D[i][next][np] = D[i][cur][p] + 1;
				Q.emplace(next, np);
			}
		}
	}

	while (Q--) {
		int a, b, c;
		cin >> a >> b >> c;
		int d = D[a][b][c & 1];
		bool ok = d <= c && d < 11111;
		if (c % 2 == 0) ok &= !G[a].empty();
		cout << (ok ? "TAK" : "NIE") << '\n';
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 98376 KB Output is correct
2 Correct 14 ms 98392 KB Output is correct
3 Correct 14 ms 98396 KB Output is correct
4 Correct 224 ms 117844 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 98392 KB Output is correct
2 Correct 14 ms 98396 KB Output is correct
3 Correct 14 ms 98396 KB Output is correct
4 Correct 235 ms 117968 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 98396 KB Output is correct
2 Correct 13 ms 98628 KB Output is correct
3 Correct 17 ms 98616 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 98648 KB Output is correct
2 Correct 14 ms 98652 KB Output is correct
3 Correct 26 ms 98652 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 98692 KB Output is correct
2 Correct 19 ms 98648 KB Output is correct
3 Correct 50 ms 98648 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 95 ms 98896 KB Output is correct
2 Correct 20 ms 98692 KB Output is correct
3 Correct 229 ms 98900 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 503 ms 116480 KB Output is correct
2 Correct 26 ms 98652 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1121 ms 116008 KB Output is correct
2 Correct 86 ms 101712 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1047 ms 117728 KB Output is correct
2 Correct 184 ms 103732 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1109 ms 117744 KB Output is correct
2 Correct 363 ms 112676 KB Output is correct