Submission #749159

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
749159	2023-05-27T12:16:13 Z	gun_gan	Cyberland (APIO23_cyberland)	C++17	100 / 100	2601 ms	16732 KB

cyberland

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

double solve(int N, int M, int K, int H, vector<int> x, vector<int>
y, vector<int> c, vector<int> arr) {
	vector<vector<pair<int,int>>> g(N);
	for(int i = 0; i < M; i++) {
		g[x[i]].push_back({y[i], c[i]});
		g[y[i]].push_back({x[i], c[i]});
	}
	priority_queue<pair<double,int>> pq;

	vector<double> dd(N, 1e18);
	
	{
		dd[0] = 0;
		pq.push({0, 0});

		while(!pq.empty()) {
			auto [x, v] = pq.top(); pq.pop();
			x = -x;
			if(dd[v] < x) continue;
			for(auto [u, w] : g[v]) {
				if(dd[u] > x + w && u != H) {
					dd[u] = x + w;
					pq.push({-dd[u], u});
				}
			} 
		}
	}

	vector<array<double, 2>> d(N, {1e18, 1e18});

	arr[0] = 0;
	for(int i = 0; i < N; i++) if(!arr[i] && dd[i] == 1e18) arr[i] = 1;

	{
		for(int i = 0; i < N; i++) {
			if(!arr[i] && dd[i] != 1e18) {
				d[i][1] = 0;
				pq.push({0, i});
			}
		}

		while(!pq.empty()) {
			auto [x, v] = pq.top(); pq.pop();
			x = -x;
			if(d[v][1] < x) continue;
			for(auto [u, w] : g[v]) {
				if(d[u][1] > x + w && u != H) {
					d[u][1] = x + w;
					pq.push({-d[u][1], u});
				}
			} 
		}
	}


	double res = 1e18;

	for(auto [u, w] : g[H]) {
		res = min(res, d[u][1] + w);
	}

	for(int k = 1; k <= min(85, K); k++) {
		vector<array<double,2>> nd(N, {1e18, 1e18});

		priority_queue<pair<double,pair<int, int>>> pq;
		for(int i = 0; i < N; i++) {
			nd[i][0] = min(d[i][0], d[i][1]);
			if(arr[i] == 2 && nd[i][0] != 1e18) {
				nd[i][0] = min(nd[i][0], d[i][1] / 2);
			}
			if(nd[i][0] != 1e18) pq.push({-nd[i][0], {i, 0}});
		}

		while(!pq.empty()) {
			auto [x, p] = pq.top(); 
			auto [v, c] = p;
			pq.pop();

			x = -x;
			if(nd[v][c] < x) continue;
			for(auto [u, w] : g[v]) {
				if(nd[u][c | 1] > x + w && u != H) {
					nd[u][c | 1] = x + w;
					pq.push({-nd[u][c | 1], {u, c | 1}});
				}
			} 
		}

		swap(nd, d);
		for(auto [u, w] : g[H]) {
			res = min(res, min(d[u][0], d[u][1]) + w);
		}
	}

	if(res == 1e18) res = -1;
	return res;
}	

// int main() {
// 	cin.tie(0); ios_base::sync_with_stdio(0);

// 	// cout << fixed << setprecision(1) << solve(4, 4, 30, 3, {0, 0, 1, 2}, {1, 2, 3, 3}, {5, 4, 2, 4}, {1, 0, 2, 1}) << '\n';
// 	// cout << fixed << setprecision(1) << solve(3, 2, 30, 2, {1, 2}, {2, 0}, {12, 4}, {1, 2, 1}) << '\n';
// 	cout << fixed << setprecision(1) << solve(4, 3, 3, 3, {0, 1, 2}, {1, 2, 3}, {11, 1, 10}, {1, 1, 2, 1}) << '\n';
// }

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	42 ms	340 KB	Correct.
2	Correct	45 ms	384 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	300 ms	456 KB	Correct.
2	Correct	352 ms	496 KB	Correct.
3	Correct	327 ms	708 KB	Correct.
4	Correct	345 ms	460 KB	Correct.
5	Correct	352 ms	524 KB	Correct.
6	Correct	410 ms	2016 KB	Correct.
7	Correct	544 ms	2012 KB	Correct.
8	Correct	234 ms	3748 KB	Correct.
9	Correct	184 ms	404 KB	Correct.
10	Correct	185 ms	412 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	410 ms	508 KB	Correct.
2	Correct	375 ms	636 KB	Correct.
3	Correct	344 ms	620 KB	Correct.
4	Correct	220 ms	540 KB	Correct.
5	Correct	217 ms	416 KB	Correct.
6	Correct	99 ms	1896 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	198 ms	8476 KB	Correct.
2	Correct	215 ms	468 KB	Correct.
3	Correct	187 ms	544 KB	Correct.
4	Correct	196 ms	492 KB	Correct.
5	Correct	123 ms	388 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	160 ms	448 KB	Correct.
2	Correct	169 ms	436 KB	Correct.
3	Correct	184 ms	500 KB	Correct.
4	Correct	244 ms	1712 KB	Correct.
5	Correct	91 ms	396 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	219 ms	460 KB	Correct.
2	Correct	176 ms	488 KB	Correct.
3	Correct	49 ms	10204 KB	Correct.
4	Correct	152 ms	1632 KB	Correct.
5	Correct	126 ms	340 KB	Correct.
6	Correct	184 ms	504 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	236 ms	460 KB	Correct.
2	Correct	29 ms	556 KB	Correct.
3	Correct	1025 ms	16412 KB	Correct.
4	Correct	631 ms	4056 KB	Correct.
5	Correct	695 ms	9604 KB	Correct.
6	Correct	306 ms	6100 KB	Correct.
7	Correct	612 ms	4364 KB	Correct.
8	Correct	472 ms	956 KB	Correct.
9	Correct	188 ms	492 KB	Correct.
10	Correct	183 ms	464 KB	Correct.
11	Correct	440 ms	720 KB	Correct.
12	Correct	205 ms	456 KB	Correct.
13	Correct	198 ms	580 KB	Correct.
14	Correct	487 ms	8460 KB	Correct.
15	Correct	506 ms	2408 KB	Correct.
16	Correct	200 ms	536 KB	Correct.
17	Correct	226 ms	524 KB	Correct.
18	Correct	220 ms	500 KB	Correct.
19	Correct	627 ms	468 KB	Correct.
20	Correct	11 ms	340 KB	Correct.
21	Correct	15 ms	340 KB	Correct.
22	Correct	21 ms	920 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	578 ms	472 KB	Correct.
2	Correct	91 ms	468 KB	Correct.
3	Correct	2243 ms	16732 KB	Correct.
4	Correct	759 ms	1384 KB	Correct.
5	Correct	1886 ms	9648 KB	Correct.
6	Correct	745 ms	6308 KB	Correct.
7	Correct	1110 ms	6816 KB	Correct.
8	Correct	678 ms	924 KB	Correct.
9	Correct	435 ms	444 KB	Correct.
10	Correct	467 ms	588 KB	Correct.
11	Correct	339 ms	552 KB	Correct.
12	Correct	490 ms	480 KB	Correct.
13	Correct	478 ms	536 KB	Correct.
14	Correct	2370 ms	8556 KB	Correct.
15	Correct	2601 ms	8756 KB	Correct.
16	Correct	1036 ms	3444 KB	Correct.
17	Correct	741 ms	1008 KB	Correct.
18	Correct	449 ms	436 KB	Correct.
19	Correct	555 ms	448 KB	Correct.
20	Correct	525 ms	676 KB	Correct.
21	Correct	1616 ms	468 KB	Correct.
22	Correct	24 ms	340 KB	Correct.
23	Correct	36 ms	420 KB	Correct.
24	Correct	50 ms	852 KB	Correct.

Submission #749159

Compilation message