oj.uz

Submission #526698

# Submission time Handle Problem Language Result Execution time Memory
526698 2022-02-16T02:15:26 Z siewjh Autobus (COCI22_autobus) C++17
30 / 70
 1000 ms 18464 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int inf = 1'000'000'007;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int nodes, edges; cin >> nodes >> edges;
	vector<vector<pair<int, int>>> adjlist(edges);
	for (int i = 0; i < edges; i++) {
		int a, b, t; cin >> a >> b >> t;
		adjlist[a].push_back({ b,t });
	}
	int maxbus, queries; cin >> maxbus >> queries;
	maxbus = min(maxbus, nodes - 1);
	int dist[71][71][71];
	for (int i = 0; i < 71; i++)
		for (int j = 0; j < 71; j++)
			for (int k = 0; k < 71; k++)
				dist[i][j][k] = inf;
	for (int i = 1; i <= nodes; i++) {
		dist[i][i][0] = 0;
		priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>, greater<pair<pair<int, int>, int>>> pq;
		pq.push({ {0,i}, 0 });
		while (!pq.empty()) {
			int d = pq.top().first.first, x = pq.top().first.second, bus = pq.top().second;
			pq.pop();
			if (d != dist[i][x][bus] || bus == maxbus) continue;
			for (auto nxt : adjlist[x]) {
				int nn = nxt.first, nd = nxt.second;
				if (d + nd < dist[i][nn][bus + 1]) {
					dist[i][nn][bus + 1] = d + nd;
					pq.push({ {dist[i][nn][bus + 1], nn}, bus + 1 });
				}
			}
		}
	}
	for (int i = 0; i < queries; i++) {
		int a, b; cin >> a >> b;
		int ans = inf;
		for (int j = 0; j <= maxbus; j++) ans = min(ans, dist[a][b][j]);
		cout << ((ans == inf) ? -1 : ans) << '\n';
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1612 KB Output is correct
2 Correct 1 ms 1612 KB Output is correct
3 Correct 1 ms 1612 KB Output is correct
4 Correct 2 ms 1612 KB Output is correct
5 Correct 1 ms 1612 KB Output is correct
6 Correct 1 ms 1612 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1740 KB Output is correct
2 Correct 3 ms 1740 KB Output is correct
3 Correct 4 ms 1740 KB Output is correct
4 Correct 5 ms 1740 KB Output is correct
5 Correct 5 ms 1740 KB Output is correct
6 Correct 5 ms 1868 KB Output is correct
7 Correct 9 ms 1868 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1612 KB Output is correct
2 Correct 1 ms 1612 KB Output is correct
3 Correct 1 ms 1612 KB Output is correct
4 Correct 2 ms 1612 KB Output is correct
5 Correct 1 ms 1612 KB Output is correct
6 Correct 1 ms 1612 KB Output is correct
7 Correct 29 ms 1768 KB Output is correct
8 Correct 94 ms 1840 KB Output is correct
9 Correct 9 ms 1740 KB Output is correct
10 Correct 79 ms 1804 KB Output is correct
11 Correct 46 ms 1956 KB Output is correct
12 Correct 161 ms 2116 KB Output is correct
13 Correct 253 ms 18028 KB Output is correct
14 Correct 370 ms 18032 KB Output is correct
15 Execution timed out 1096 ms 18464 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1612 KB Output is correct
2 Correct 1 ms 1612 KB Output is correct
3 Correct 1 ms 1612 KB Output is correct
4 Correct 2 ms 1612 KB Output is correct
5 Correct 1 ms 1612 KB Output is correct
6 Correct 1 ms 1612 KB Output is correct
7 Correct 2 ms 1740 KB Output is correct
8 Correct 3 ms 1740 KB Output is correct
9 Correct 4 ms 1740 KB Output is correct
10 Correct 5 ms 1740 KB Output is correct
11 Correct 5 ms 1740 KB Output is correct
12 Correct 5 ms 1868 KB Output is correct
13 Correct 9 ms 1868 KB Output is correct
14 Correct 29 ms 1768 KB Output is correct
15 Correct 94 ms 1840 KB Output is correct
16 Correct 9 ms 1740 KB Output is correct
17 Correct 79 ms 1804 KB Output is correct
18 Correct 46 ms 1956 KB Output is correct
19 Correct 161 ms 2116 KB Output is correct
20 Correct 253 ms 18028 KB Output is correct
21 Correct 370 ms 18032 KB Output is correct
22 Execution timed out 1096 ms 18464 KB Time limit exceeded
23 Halted 0 ms 0 KB -