Submission #928159

#	Time	Username	Problem	Language	Result	Execution time	Memory
928159		TAhmed33	Tales of seafaring (POI13_mor)	C++98	100 / 100	1131 ms	41248 KiB

mor

#include <bits/stdc++.h>
using namespace std;
int dist[5001][2];
int ans[1000001];
int n, m, q;
vector <array <int, 3>> queries[5001];
vector <int> adj[5001];
int main () {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> q;
	for (int i = 1; i <= m; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	for (int i = 1; i <= q; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		queries[a].push_back({b, c, i});
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			dist[j][0] = dist[j][1] = 2e9;
		}
		queue <pair <int, int>> cur;
		cur.push({i, 0}); dist[i][0] = 0;
		while (!cur.empty()) {
			auto k = cur.front();
			cur.pop();
			for (auto j : adj[k.first]) {
				if (dist[j][k.second ^ 1] > dist[k.first][k.second] + 1) {
					dist[j][k.second ^ 1] = dist[k.first][k.second] + 1;
					cur.push({j, k.second ^ 1});
				}
			}
		}
		for (auto j : queries[i]) {
			ans[j[2]] = dist[j[0]][j[1] & 1] <= j[1] && !adj[i].empty();
		}
	}
	for (int i = 1; i <= q; i++) cout << (ans[i] ? "TAK\n" : "NIE\n");
}

• 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