oj.uz

Submission #1008090

# Submission time Handle Problem Language Result Execution time Memory
1008090 2024-06-26T07:33:17 Z overwatch9 Swapping Cities (APIO20_swap) C++17
0 / 100
 249 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;
	queue <array <int, 3>> pq;
	pq.push({0, x, y});
	vector <vector <bool>> processed(n, vector <bool> (n));
	while (!pq.empty()) {
		int a = pq.front()[1], b = pq.front()[2];
		pq.pop();
		if (processed[a][b])
			continue;
		processed[a][b] = true;
		for (auto i : adj[a]) {
			for (auto j : adj[b]) {
				int d = max({dis[a][b], i.second, j.second});
				if (d < dis[i.first][j.first] && i.first != j.first && (i.first != b || j.first != a)) {
					dis[i.first][j.first] = d;
					pq.push({-d, i.first, j.first});
				}
				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});
				}
				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 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 16 ms 1284 KB Output is correct
5 Correct 74 ms 4212 KB Output is correct
6 Correct 86 ms 3672 KB Output is correct
7 Correct 107 ms 4440 KB Output is correct
8 Correct 107 ms 4692 KB Output is correct
9 Runtime error 215 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 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Runtime error 237 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 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 16 ms 1284 KB Output is correct
5 Correct 74 ms 4212 KB Output is correct
6 Correct 86 ms 3672 KB Output is correct
7 Correct 107 ms 4440 KB Output is correct
8 Correct 107 ms 4692 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 176 ms 5444 KB Output is correct
11 Correct 217 ms 4700 KB Output is correct
12 Correct 206 ms 4444 KB Output is correct
13 Correct 140 ms 3436 KB Output is correct
14 Correct 159 ms 4036 KB Output is correct
15 Correct 214 ms 4700 KB Output is correct
16 Correct 249 ms 4700 KB Output is correct
17 Correct 226 ms 4696 KB Output is correct
18 Correct 217 ms 5080 KB Output is correct
19 Incorrect 181 ms 7716 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 16 ms 1284 KB Output is correct
6 Correct 74 ms 4212 KB Output is correct
7 Correct 86 ms 3672 KB Output is correct
8 Correct 107 ms 4440 KB Output is correct
9 Correct 107 ms 4692 KB Output is correct
10 Runtime error 215 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 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 16 ms 1284 KB Output is correct
5 Correct 74 ms 4212 KB Output is correct
6 Correct 86 ms 3672 KB Output is correct
7 Correct 107 ms 4440 KB Output is correct
8 Correct 107 ms 4692 KB Output is correct
9 Runtime error 215 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 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 16 ms 1284 KB Output is correct
6 Correct 74 ms 4212 KB Output is correct
7 Correct 86 ms 3672 KB Output is correct
8 Correct 107 ms 4440 KB Output is correct
9 Correct 107 ms 4692 KB Output is correct
10 Runtime error 215 ms 524288 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -