Submission #962016

#	Time	Username	Problem	Language	Result	Execution time	Memory
962016		IBory	Tales of seafaring (POI13_mor)	C++17	100 / 100	1121 ms	117968 KiB

mor

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10