Submission #759229

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
759229	2023-06-15T22:02:38 Z	ymm	Cyberland (APIO23_cyberland)	C++17	100 / 100	1679 ms	14240 KB

cyberland

#include "cyberland.h"

#include <bits/stdc++.h>
#define Loop(x, l, r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

const double inf = 1e100;
const int N = 100'010;
vector<pii> A[N];
int n;

vector<double> dij(vector<double> dis, int dst)
{
	priority_queue<pair<double,int>, vector<pair<double,int>>, greater<pair<double,int>>> Q;
	Loop (i,0,n)
		Q.push({dis[i], i});
	while (Q.size()) {
		auto [d, v] = Q.top();
		Q.pop();
		if (d != dis[v])
			continue;
		if (v == dst)
			continue;
		for (auto [u, w] : A[v]) {
			if (d + w >= dis[u])
				continue;
			dis[u] = d + w;
			Q.push({dis[u], u});
		}
	}
	return dis;
}

double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
	n = N;
	Loop (i,0,n)
		A[i].clear();
	Loop (i,0,M) {
		int v = x[i], u = y[i], w = c[i];
		A[v].push_back({u, w});
		A[u].push_back({v, w});
	}
	vector<double> dis(n, inf);
	dis[0] = 0;
	dis = dij(dis, H);
	if (dis[H] == inf)
		return -1;
	Loop (i,0,n)
		dis[i] = dis[i] != inf && arr[i] == 0? 0: inf;
	dis[0] = 0;
	double ans = inf;
	Loop (_,0,min(K+1,90)) {
		dis = dij(dis, H);
		ans = min(ans, dis[H]);
		vector<double> dis2(n, inf);
		Loop (v,0,n) {
			if (arr[v] != 2)
				continue;
			for (auto [u, w] : A[v])
				dis2[u] = min(dis2[u], dis[v]/2 + w);
		}
		dis = dis2;
	}
	return ans;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	2768 KB	Correct.
2	Correct	40 ms	2724 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	105 ms	2832 KB	Correct.
2	Correct	128 ms	2812 KB	Correct.
3	Correct	123 ms	2804 KB	Correct.
4	Correct	129 ms	2832 KB	Correct.
5	Correct	125 ms	2828 KB	Correct.
6	Correct	133 ms	3972 KB	Correct.
7	Correct	187 ms	3944 KB	Correct.
8	Correct	75 ms	5116 KB	Correct.
9	Correct	83 ms	2744 KB	Correct.
10	Correct	80 ms	2740 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	125 ms	2756 KB	Correct.
2	Correct	118 ms	2856 KB	Correct.
3	Correct	108 ms	2804 KB	Correct.
4	Correct	86 ms	2644 KB	Correct.
5	Correct	85 ms	2736 KB	Correct.
6	Correct	29 ms	3668 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	376 ms	9260 KB	Correct.
2	Correct	241 ms	2756 KB	Correct.
3	Correct	223 ms	2788 KB	Correct.
4	Correct	226 ms	2752 KB	Correct.
5	Correct	129 ms	2644 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	63 ms	2888 KB	Correct.
2	Correct	66 ms	2836 KB	Correct.
3	Correct	66 ms	2900 KB	Correct.
4	Correct	94 ms	3880 KB	Correct.
5	Correct	44 ms	2740 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	71 ms	2908 KB	Correct.
2	Correct	51 ms	2832 KB	Correct.
3	Correct	42 ms	11176 KB	Correct.
4	Correct	51 ms	3668 KB	Correct.
5	Correct	56 ms	2736 KB	Correct.
6	Correct	60 ms	2892 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	129 ms	2772 KB	Correct.
2	Correct	19 ms	2872 KB	Correct.
3	Correct	599 ms	14240 KB	Correct.
4	Correct	420 ms	5560 KB	Correct.
5	Correct	425 ms	9560 KB	Correct.
6	Correct	127 ms	7500 KB	Correct.
7	Correct	419 ms	5576 KB	Correct.
8	Correct	354 ms	3200 KB	Correct.
9	Correct	125 ms	2864 KB	Correct.
10	Correct	115 ms	2812 KB	Correct.
11	Correct	303 ms	3028 KB	Correct.
12	Correct	142 ms	2920 KB	Correct.
13	Correct	124 ms	2828 KB	Correct.
14	Correct	404 ms	8512 KB	Correct.
15	Correct	400 ms	4272 KB	Correct.
16	Correct	112 ms	2900 KB	Correct.
17	Correct	153 ms	2832 KB	Correct.
18	Correct	134 ms	2820 KB	Correct.
19	Correct	418 ms	2808 KB	Correct.
20	Correct	7 ms	2708 KB	Correct.
21	Correct	10 ms	2764 KB	Correct.
22	Correct	15 ms	3116 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	310 ms	2876 KB	Correct.
2	Correct	44 ms	2852 KB	Correct.
3	Correct	1474 ms	14124 KB	Correct.
4	Correct	508 ms	3576 KB	Correct.
5	Correct	1054 ms	9556 KB	Correct.
6	Correct	305 ms	7584 KB	Correct.
7	Correct	822 ms	7624 KB	Correct.
8	Correct	465 ms	3068 KB	Correct.
9	Correct	230 ms	2868 KB	Correct.
10	Correct	215 ms	2804 KB	Correct.
11	Correct	251 ms	2808 KB	Correct.
12	Correct	307 ms	2828 KB	Correct.
13	Correct	251 ms	2884 KB	Correct.
14	Correct	1679 ms	8900 KB	Correct.
15	Correct	1646 ms	8668 KB	Correct.
16	Correct	684 ms	5064 KB	Correct.
17	Correct	530 ms	3216 KB	Correct.
18	Correct	226 ms	2920 KB	Correct.
19	Correct	340 ms	2820 KB	Correct.
20	Correct	281 ms	2824 KB	Correct.
21	Correct	1059 ms	2844 KB	Correct.
22	Correct	12 ms	2644 KB	Correct.
23	Correct	17 ms	2752 KB	Correct.
24	Correct	22 ms	3232 KB	Correct.

Submission #759229

Compilation message