oj.uz

Submission #928158

# Submission time Handle Problem Language Result Execution time Memory
928158 2024-02-15T22:36:36 Z TAhmed33 Tales of seafaring (POI13_mor) C++
60 / 100
 1081 ms 41788 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];
		}
	}
	for (int i = 1; i <= q; i++) cout << (ans[i] ? "TAK\n" : "NIE\n");
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Incorrect 2 ms 2652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2804 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Incorrect 1 ms 2652 KB Output isn't correct
4 Halted 0 ms 0 KB -

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 2648 KB Output is correct
3 Correct 1 ms 2648 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 2 ms 2652 KB Output is correct
3 Correct 13 ms 2652 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3164 KB Output is correct
2 Correct 6 ms 2908 KB Output is correct
3 Incorrect 39 ms 3088 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 3420 KB Output is correct
2 Correct 7 ms 2904 KB Output is correct
3 Incorrect 217 ms 3164 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 40640 KB Output is correct
2 Correct 13 ms 2648 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1004 ms 41788 KB Output is correct
2 Correct 56 ms 9924 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 896 ms 36980 KB Output is correct
2 Correct 130 ms 13208 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1081 ms 37236 KB Output is correct
2 Correct 240 ms 31824 KB Output is correct