Submission #749157

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
749157	2023-05-27T12:15:04 Z	gun_gan	Cyberland (APIO23_cyberland)	C++17	97 / 100	3000 ms	16644 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(100, 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	45 ms	340 KB	Correct.
2	Correct	47 ms	388 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	297 ms	460 KB	Correct.
2	Correct	356 ms	452 KB	Correct.
3	Correct	339 ms	460 KB	Correct.
4	Correct	353 ms	468 KB	Correct.
5	Correct	374 ms	528 KB	Correct.
6	Correct	413 ms	2012 KB	Correct.
7	Correct	537 ms	2004 KB	Correct.
8	Correct	245 ms	3748 KB	Correct.
9	Correct	177 ms	524 KB	Correct.
10	Correct	189 ms	400 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	390 ms	624 KB	Correct.
2	Correct	382 ms	484 KB	Correct.
3	Correct	346 ms	568 KB	Correct.
4	Correct	207 ms	520 KB	Correct.
5	Correct	206 ms	388 KB	Correct.
6	Correct	95 ms	1904 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	219 ms	8500 KB	Correct.
2	Correct	218 ms	512 KB	Correct.
3	Correct	207 ms	484 KB	Correct.
4	Correct	199 ms	520 KB	Correct.
5	Correct	128 ms	400 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	161 ms	460 KB	Correct.
2	Correct	160 ms	452 KB	Correct.
3	Correct	177 ms	452 KB	Correct.
4	Correct	232 ms	1708 KB	Correct.
5	Correct	93 ms	340 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	244 ms	460 KB	Correct.
2	Correct	173 ms	508 KB	Correct.
3	Correct	62 ms	10188 KB	Correct.
4	Correct	164 ms	1636 KB	Correct.
5	Correct	129 ms	408 KB	Correct.
6	Correct	204 ms	468 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	261 ms	428 KB	Correct.
2	Correct	32 ms	556 KB	Correct.
3	Correct	1147 ms	16384 KB	Correct.
4	Correct	715 ms	3976 KB	Correct.
5	Correct	892 ms	9564 KB	Correct.
6	Correct	330 ms	6112 KB	Correct.
7	Correct	717 ms	4340 KB	Correct.
8	Correct	561 ms	1008 KB	Correct.
9	Correct	213 ms	460 KB	Correct.
10	Correct	211 ms	468 KB	Correct.
11	Correct	498 ms	684 KB	Correct.
12	Correct	226 ms	460 KB	Correct.
13	Correct	248 ms	584 KB	Correct.
14	Correct	588 ms	8412 KB	Correct.
15	Correct	576 ms	2412 KB	Correct.
16	Correct	210 ms	420 KB	Correct.
17	Correct	244 ms	488 KB	Correct.
18	Correct	244 ms	608 KB	Correct.
19	Correct	727 ms	468 KB	Correct.
20	Correct	12 ms	384 KB	Correct.
21	Correct	17 ms	340 KB	Correct.
22	Correct	24 ms	852 KB	Correct.

Subtask #8
0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	664 ms	472 KB	Correct.
2	Correct	88 ms	468 KB	Correct.
3	Correct	2612 ms	16644 KB	Correct.
4	Correct	786 ms	1380 KB	Correct.
5	Correct	2394 ms	9680 KB	Correct.
6	Correct	943 ms	6312 KB	Correct.
7	Correct	1293 ms	6744 KB	Correct.
8	Correct	770 ms	860 KB	Correct.
9	Correct	514 ms	544 KB	Correct.
10	Correct	509 ms	736 KB	Correct.
11	Correct	370 ms	652 KB	Correct.
12	Correct	573 ms	556 KB	Correct.
13	Correct	588 ms	640 KB	Correct.
14	Correct	2721 ms	8632 KB	Correct.
15	Execution timed out	3074 ms	8804 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-

Submission #749157

Compilation message