oj.uz

Submission #1008120

# Submission time Handle Problem Language Result Execution time Memory
1008120 2024-06-26T07:47:25 Z overwatch9 Swapping Cities (APIO20_swap) C++17
17 / 100
 1706 ms 34536 KB 
#include "swap.h"

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

vector <vector <pair <int, int>>> adj;
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]});
	}
}
const int maxn = 1001;
int dis[maxn][maxn];
priority_queue <array <int, 3>> pq;
int processed[maxn][maxn];
int cnt = 0;
int getMinimumFuelCapacity(int x, int y) {
	for (int i = 0; i < n; i++)
		fill(dis[i], dis[i] + n + 1, 1e9 + 1);
	dis[x][y] = 0;
	cnt++;
	pq.push({0, x, y});
	while (!pq.empty()) {
		int a = pq.top()[1], b = pq.top()[2];
		pq.pop();
		if (processed[a][b] == cnt)
			continue;
		processed[a][b] = cnt;
		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 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 59 ms 6756 KB Output is correct
5 Correct 211 ms 9872 KB Output is correct
6 Correct 233 ms 9424 KB Output is correct
7 Correct 311 ms 12756 KB Output is correct
8 Correct 293 ms 9164 KB Output is correct
9 Runtime error 55 ms 24244 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Runtime error 86 ms 34536 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 59 ms 6756 KB Output is correct
5 Correct 211 ms 9872 KB Output is correct
6 Correct 233 ms 9424 KB Output is correct
7 Correct 311 ms 12756 KB Output is correct
8 Correct 293 ms 9164 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 564 ms 15952 KB Output is correct
11 Correct 607 ms 11816 KB Output is correct
12 Correct 650 ms 11360 KB Output is correct
13 Correct 502 ms 10744 KB Output is correct
14 Correct 504 ms 9420 KB Output is correct
15 Correct 665 ms 9424 KB Output is correct
16 Correct 618 ms 9936 KB Output is correct
17 Correct 599 ms 9680 KB Output is correct
18 Correct 736 ms 16320 KB Output is correct
19 Correct 422 ms 10260 KB Output is correct
20 Correct 626 ms 11372 KB Output is correct
21 Correct 842 ms 14544 KB Output is correct
22 Correct 140 ms 7132 KB Output is correct
23 Correct 552 ms 11716 KB Output is correct
24 Correct 1579 ms 21188 KB Output is correct
25 Correct 1336 ms 22000 KB Output is correct
26 Correct 1706 ms 21604 KB Output is correct
27 Correct 606 ms 9784 KB Output is correct
28 Correct 1435 ms 20564 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 59 ms 6756 KB Output is correct
6 Correct 211 ms 9872 KB Output is correct
7 Correct 233 ms 9424 KB Output is correct
8 Correct 311 ms 12756 KB Output is correct
9 Correct 293 ms 9164 KB Output is correct
10 Runtime error 55 ms 24244 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 59 ms 6756 KB Output is correct
5 Correct 211 ms 9872 KB Output is correct
6 Correct 233 ms 9424 KB Output is correct
7 Correct 311 ms 12756 KB Output is correct
8 Correct 293 ms 9164 KB Output is correct
9 Runtime error 55 ms 24244 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 59 ms 6756 KB Output is correct
6 Correct 211 ms 9872 KB Output is correct
7 Correct 233 ms 9424 KB Output is correct
8 Correct 311 ms 12756 KB Output is correct
9 Correct 293 ms 9164 KB Output is correct
10 Runtime error 55 ms 24244 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -