oj.uz

Submission #928159

# Submission time Handle Problem Language Result Execution time Memory
928159 2024-02-15T22:38:46 Z TAhmed33 Tales of seafaring (POI13_mor) C++
100 / 100
 1131 ms 41248 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 0 ms 2652 KB Output is correct
4 Correct 191 ms 40900 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 207 ms 41248 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 13 ms 3060 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2928 KB Output is correct
2 Correct 6 ms 2908 KB Output is correct
3 Correct 41 ms 2948 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 3164 KB Output is correct
2 Correct 7 ms 2864 KB Output is correct
3 Correct 210 ms 3000 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 26852 KB Output is correct
2 Correct 14 ms 2652 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1047 ms 28308 KB Output is correct
2 Correct 65 ms 7516 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 955 ms 21944 KB Output is correct
2 Correct 118 ms 9392 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1131 ms 22132 KB Output is correct
2 Correct 241 ms 20776 KB Output is correct