Submission #750800

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
750800	2023-05-30T10:13:32 Z	rxlfd314	Cyberland (APIO23_cyberland)	C++17	100 / 100	1236 ms	74968 KB

cyberland

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

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
	vector<pair<int, double>> adj[N];
	for (int i = 0; i < M; i++) {
		adj[x[i]].push_back({y[i], (double)c[i]});
		adj[y[i]].push_back({x[i], (double)c[i]});
	}
	
	bool useful[N] = {};
	queue<int> qu;
	qu.push(0);
	useful[0] = true;
	while (qu.size()) {
		int f = qu.front();
		qu.pop();
		if (f == H) continue;
		for (auto [nf, _] : adj[f]) {
			if (!useful[nf]) {
				useful[nf] = true;
				qu.push(nf);
			}
		}
	}
	
	if (!useful[H]) return -1;
	
	vector<vector<double>> dst(min(K, 80)+1, vector<double>(N, 1e14));
	double ans = 1e14;
	for (int ii = 0; ii <= min(K, 80); ii++) {
		priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;
		for (int i = 0; i < N; i++) {
			if (!useful[i]) continue;
			if (arr[i] == 2 && ii) {
				for (auto [j, v] : adj[i]) {
					if (!useful[j] || j == H) continue;
					dst[ii][i] = min(dst[ii][i], (dst[ii-1][j] + v) / 2.0);
				}
				pq.push({dst[ii][i], i});
			} else if (!arr[i]) {
				dst[ii][i] = 0;
				pq.push({0, i});
			}
		}
		if (!ii) {
			dst[0][0] = 0;
			pq.push({0, 0});
		}
		
		while (pq.size()) {
			auto [d, f] = pq.top();
			pq.pop();
			if (d > dst[ii][f] || f == H) continue;
			for (auto [nf, v] : adj[f]) {
				if (d + v < dst[ii][nf] && useful[nf]) {
					dst[ii][nf] = d + v;
					pq.push({d+v, nf});
				}
			}
		}
		
		ans = min(ans, dst[ii][H]);
	}
	
	return ans;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	452 KB	Correct.
2	Correct	29 ms	468 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	724 KB	Correct.
2	Correct	33 ms	700 KB	Correct.
3	Correct	32 ms	752 KB	Correct.
4	Correct	38 ms	680 KB	Correct.
5	Correct	35 ms	692 KB	Correct.
6	Correct	29 ms	3700 KB	Correct.
7	Correct	37 ms	3684 KB	Correct.
8	Correct	16 ms	7380 KB	Correct.
9	Correct	29 ms	468 KB	Correct.
10	Correct	29 ms	496 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	145 ms	848 KB	Correct.
2	Correct	137 ms	668 KB	Correct.
3	Correct	132 ms	708 KB	Correct.
4	Correct	92 ms	468 KB	Correct.
5	Correct	91 ms	484 KB	Correct.
6	Correct	43 ms	3364 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	20856 KB	Correct.
2	Correct	96 ms	700 KB	Correct.
3	Correct	94 ms	784 KB	Correct.
4	Correct	87 ms	688 KB	Correct.
5	Correct	62 ms	492 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	680 KB	Correct.
2	Correct	28 ms	664 KB	Correct.
3	Correct	29 ms	664 KB	Correct.
4	Correct	28 ms	3484 KB	Correct.
5	Correct	24 ms	432 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	81 ms	724 KB	Correct.
2	Correct	61 ms	704 KB	Correct.
3	Correct	42 ms	8568 KB	Correct.
4	Correct	69 ms	2608 KB	Correct.
5	Correct	53 ms	484 KB	Correct.
6	Correct	72 ms	688 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	94 ms	648 KB	Correct.
2	Correct	17 ms	852 KB	Correct.
3	Correct	438 ms	24628 KB	Correct.
4	Correct	292 ms	6456 KB	Correct.
5	Correct	324 ms	17132 KB	Correct.
6	Correct	140 ms	9240 KB	Correct.
7	Correct	261 ms	6556 KB	Correct.
8	Correct	206 ms	1436 KB	Correct.
9	Correct	73 ms	684 KB	Correct.
10	Correct	69 ms	668 KB	Correct.
11	Correct	192 ms	768 KB	Correct.
12	Correct	82 ms	648 KB	Correct.
13	Correct	87 ms	688 KB	Correct.
14	Correct	245 ms	8224 KB	Correct.
15	Correct	256 ms	2520 KB	Correct.
16	Correct	85 ms	620 KB	Correct.
17	Correct	95 ms	772 KB	Correct.
18	Correct	80 ms	680 KB	Correct.
19	Correct	225 ms	724 KB	Correct.
20	Correct	5 ms	340 KB	Correct.
21	Correct	6 ms	468 KB	Correct.
22	Correct	10 ms	1212 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	172 ms	1008 KB	Correct.
2	Correct	29 ms	1108 KB	Correct.
3	Correct	273 ms	74968 KB	Correct.
4	Correct	284 ms	3412 KB	Correct.
5	Correct	817 ms	31312 KB	Correct.
6	Correct	302 ms	13316 KB	Correct.
7	Correct	539 ms	14352 KB	Correct.
8	Correct	261 ms	1416 KB	Correct.
9	Correct	151 ms	1116 KB	Correct.
10	Correct	126 ms	972 KB	Correct.
11	Correct	199 ms	548 KB	Correct.
12	Correct	161 ms	1024 KB	Correct.
13	Correct	155 ms	1024 KB	Correct.
14	Correct	1236 ms	31200 KB	Correct.
15	Correct	981 ms	37492 KB	Correct.
16	Correct	426 ms	11584 KB	Correct.
17	Correct	296 ms	3000 KB	Correct.
18	Correct	145 ms	1208 KB	Correct.
19	Correct	208 ms	1108 KB	Correct.
20	Correct	156 ms	1016 KB	Correct.
21	Correct	491 ms	1176 KB	Correct.
22	Correct	8 ms	340 KB	Correct.
23	Correct	12 ms	664 KB	Correct.
24	Correct	20 ms	1608 KB	Correct.

Submission #750800

Compilation message