oj.uz

Submission #1008106

# Submission time Handle Problem Language Result Execution time Memory
1008106 2024-06-26T07:40:50 Z overwatch9 Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 524288 KB 
#include "swap.h"

#include <bits/stdc++.h>
using namespace std;

vector <vector <pair <int, int>>> adj;
vector <array <int, 3>> edges;
int n, m;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
    adj.resize(N+1);
	n = N;
	m = M;
    for (int i = 0; i < M; i++) {
        adj[U[i]].push_back({V[i], W[i]});
		adj[V[i]].push_back({U[i], W[i]});
		edges.push_back({U[i], V[i], W[i]});
		edges.push_back({V[i], U[i], W[i]});
	}
}

int getMinimumFuelCapacity(int x, int y) {
	vector <vector <int>> dis(n, vector <int> (n, 1e9 + 1));
	dis[x][y] = 0;
	priority_queue <array <int, 3>> pq;
	pq.push({0, x, y});
	vector <vector <bool>> processed(n, vector <bool> (n));
	while (!pq.empty()) {
		int a = pq.top()[1], b = pq.top()[2];
		pq.pop();
		if (processed[a][b])
			continue;
		processed[a][b] = true;
		for (auto i : adj[a]) {
			int d = max(dis[a][b], i.second);
			if (d < dis[i.first][b] && i.first != b) {
				dis[i.first][b] = d;
				pq.push({-d, i.first, b});
			}
		}
		for (auto j : adj[b]) {
			int d = max(dis[a][b], j.second);
			if (d < dis[a][j.first] && a != j.first) {
				dis[a][j.first] = d;
				pq.push({-d, a, j.first});
			}
		}
	}
	if (dis[y][x] == 1e9 + 1)
		dis[y][x] = -1;
	return dis[y][x];
}
// int main() {
// 	int N, M;
// 	cin >> N >> M;
// 	vector <int> u(M), v(M), w(M);
// 	for (int i = 0; i < M; i++)
// 		cin >> u[i] >> v[i] >> w[i];
// 	init(N, M, u, v, w);
// 	int q;
// 	cin >> q;
// 	while (q--) {
// 		int x, y;
// 		cin >> x >> y;
// 		cout << getMinimumFuelCapacity(x, y) << '\n';
// 	}
// }

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 56 ms 1728 KB Output is correct
5 Correct 257 ms 6396 KB Output is correct
6 Correct 238 ms 6156 KB Output is correct
7 Correct 370 ms 9304 KB Output is correct
8 Correct 306 ms 5944 KB Output is correct
9 Runtime error 233 ms 524288 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 239 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 56 ms 1728 KB Output is correct
5 Correct 257 ms 6396 KB Output is correct
6 Correct 238 ms 6156 KB Output is correct
7 Correct 370 ms 9304 KB Output is correct
8 Correct 306 ms 5944 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 618 ms 10996 KB Output is correct
11 Correct 669 ms 8380 KB Output is correct
12 Correct 699 ms 9900 KB Output is correct
13 Correct 488 ms 7672 KB Output is correct
14 Correct 543 ms 5892 KB Output is correct
15 Correct 713 ms 6168 KB Output is correct
16 Correct 714 ms 6932 KB Output is correct
17 Correct 740 ms 7368 KB Output is correct
18 Correct 812 ms 11064 KB Output is correct
19 Correct 440 ms 8680 KB Output is correct
20 Correct 732 ms 10704 KB Output is correct
21 Correct 1046 ms 15276 KB Output is correct
22 Correct 147 ms 3780 KB Output is correct
23 Correct 551 ms 7968 KB Output is correct
24 Correct 1918 ms 26948 KB Output is correct
25 Correct 1567 ms 17360 KB Output is correct
26 Execution timed out 2024 ms 29112 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 56 ms 1728 KB Output is correct
6 Correct 257 ms 6396 KB Output is correct
7 Correct 238 ms 6156 KB Output is correct
8 Correct 370 ms 9304 KB Output is correct
9 Correct 306 ms 5944 KB Output is correct
10 Runtime error 233 ms 524288 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 56 ms 1728 KB Output is correct
5 Correct 257 ms 6396 KB Output is correct
6 Correct 238 ms 6156 KB Output is correct
7 Correct 370 ms 9304 KB Output is correct
8 Correct 306 ms 5944 KB Output is correct
9 Runtime error 233 ms 524288 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 56 ms 1728 KB Output is correct
6 Correct 257 ms 6396 KB Output is correct
7 Correct 238 ms 6156 KB Output is correct
8 Correct 370 ms 9304 KB Output is correct
9 Correct 306 ms 5944 KB Output is correct
10 Runtime error 233 ms 524288 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -