Submission #768176

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
768176	2023-06-27T16:27:25 Z	green_gold_dog	Cyberland (APIO23_cyberland)	C++17	100 / 100	1889 ms	23796 KB

cyberland

#include "cyberland.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF = 1'000'000'000'000'000'000;

void dfs(ll v, ll h, vector<vector<pair<ll, ll>>>& g, vector<bool>& used) {
	used[v] = true;
	if (v == h) {
		return;
	}
	for (auto[i, _] : g[v]) {
		if (!used[i]) {
			dfs(i, h, g, used);
		}
	}
}

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<ll, ll>>> g(n);
	for (ll i = 0; i < m; i++) {
		g[x[i]].emplace_back(y[i], c[i]);
		g[y[i]].emplace_back(x[i], c[i]);
	}
	vector<bool> used(n, false);
	dfs(0, h, g, used);
	if (!used[h]) {
		return -1;
	}
	vector<double> dist(n, INF);
	dist[0] = 0;
	for (ll i = 0; i < n; i++) {
		if (arr[i] == 0 && used[i]) {
			dist[i] = 0;
		}
	}
	if (k > 70) {
		k = 70;
	}
	for (ll nd = 0; nd <= k; nd++) {
		set<pair<double, ll>> pq;
		for (ll i = 0; i < n; i++) {
			if (dist[i] != INF) {
				pq.insert(make_pair(dist[i], i));
			}
		}
		while (!pq.empty()) {
			auto[d, v] = *pq.begin();
			pq.erase(pq.begin());
			if (v == h) {
				continue;
			}
			for (auto[i, c] : g[v]) {
				if (c + d < dist[i]) {
					pq.erase(make_pair(dist[i], i));
					dist[i] = c + d;
					pq.insert(make_pair(dist[i], i));
				}
			}
		}
		if (nd == k) {
			continue;
		}
		vector<pair<ll, double>> upd;
		for (ll i = 0; i < n; i++) {
			if (arr[i] == 2 && dist[i] != INF) {
				dist[i] /= 2;
				for (auto[v, c] : g[i]) {
					upd.emplace_back(v, c + dist[i]);
				}
				dist[i] = INF;
			}
		}
		for (auto[v, d] : upd) {
			if (dist[v] > d) {
				dist[v] = d;
			}
		}
	}
	return dist[h];
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	460 KB	Correct.
2	Correct	34 ms	388 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	159 ms	524 KB	Correct.
2	Correct	193 ms	492 KB	Correct.
3	Correct	184 ms	488 KB	Correct.
4	Correct	198 ms	592 KB	Correct.
5	Correct	189 ms	524 KB	Correct.
6	Correct	237 ms	1972 KB	Correct.
7	Correct	311 ms	1936 KB	Correct.
8	Correct	148 ms	3668 KB	Correct.
9	Correct	113 ms	376 KB	Correct.
10	Correct	111 ms	376 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	191 ms	480 KB	Correct.
2	Correct	181 ms	468 KB	Correct.
3	Correct	164 ms	492 KB	Correct.
4	Correct	124 ms	360 KB	Correct.
5	Correct	127 ms	376 KB	Correct.
6	Correct	43 ms	1620 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	142 ms	8472 KB	Correct.
2	Correct	153 ms	508 KB	Correct.
3	Correct	138 ms	528 KB	Correct.
4	Correct	150 ms	544 KB	Correct.
5	Correct	87 ms	380 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	71 ms	480 KB	Correct.
2	Correct	73 ms	504 KB	Correct.
3	Correct	81 ms	528 KB	Correct.
4	Correct	118 ms	1660 KB	Correct.
5	Correct	49 ms	384 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	82 ms	524 KB	Correct.
2	Correct	59 ms	492 KB	Correct.
3	Correct	33 ms	8532 KB	Correct.
4	Correct	70 ms	1688 KB	Correct.
5	Correct	58 ms	340 KB	Correct.
6	Correct	71 ms	508 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	132 ms	432 KB	Correct.
2	Correct	20 ms	596 KB	Correct.
3	Correct	953 ms	17676 KB	Correct.
4	Correct	580 ms	4060 KB	Correct.
5	Correct	492 ms	11964 KB	Correct.
6	Correct	171 ms	8812 KB	Correct.
7	Correct	535 ms	4560 KB	Correct.
8	Correct	388 ms	1008 KB	Correct.
9	Correct	108 ms	584 KB	Correct.
10	Correct	98 ms	504 KB	Correct.
11	Correct	320 ms	664 KB	Correct.
12	Correct	127 ms	464 KB	Correct.
13	Correct	122 ms	544 KB	Correct.
14	Correct	465 ms	9064 KB	Correct.
15	Correct	437 ms	2552 KB	Correct.
16	Correct	111 ms	460 KB	Correct.
17	Correct	146 ms	516 KB	Correct.
18	Correct	127 ms	484 KB	Correct.
19	Correct	370 ms	492 KB	Correct.
20	Correct	7 ms	340 KB	Correct.
21	Correct	9 ms	340 KB	Correct.
22	Correct	13 ms	1268 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	260 ms	520 KB	Correct.
2	Correct	40 ms	596 KB	Correct.
3	Correct	1061 ms	23796 KB	Correct.
4	Correct	569 ms	1472 KB	Correct.
5	Correct	1058 ms	11924 KB	Correct.
6	Correct	366 ms	9012 KB	Correct.
7	Correct	773 ms	7300 KB	Correct.
8	Correct	446 ms	732 KB	Correct.
9	Correct	214 ms	444 KB	Correct.
10	Correct	189 ms	616 KB	Correct.
11	Correct	234 ms	464 KB	Correct.
12	Correct	250 ms	468 KB	Correct.
13	Correct	243 ms	604 KB	Correct.
14	Correct	1602 ms	10252 KB	Correct.
15	Correct	1889 ms	9012 KB	Correct.
16	Correct	881 ms	3612 KB	Correct.
17	Correct	547 ms	1012 KB	Correct.
18	Correct	213 ms	480 KB	Correct.
19	Correct	292 ms	540 KB	Correct.
20	Correct	240 ms	456 KB	Correct.
21	Correct	776 ms	496 KB	Correct.
22	Correct	11 ms	340 KB	Correct.
23	Correct	16 ms	420 KB	Correct.
24	Correct	25 ms	1272 KB	Correct.

Submission #768176

Compilation message