Submission #919224

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
919224	2024-01-31T13:11:25 Z	MisterReaper	Cyberland (APIO23_cyberland)	C++17	100 / 100	1884 ms	84736 KB

cyberland

#include <bits/stdc++.h>
//#include "cyberland.h"
using i64 = long long;

struct DSU {
	int n;
	std::vector<int> par;
	DSU(int _n) : n(_n) {
		par.resize(n);
		std::iota(par.begin(), par.end(), 0);
	}

	int get(int x) {
		if(par[x] == x) {
			return x;
		}

		return par[x] = get(par[x]);
	}

	bool same(int a, int b) {
		return get(a) == get(b);
	}

	bool unite(int u, int v) {
		if(same(u, v)) {
			return false;
		}

		u = get(u);
		v = get(v);
		par[u] = v;

		return true;
	}
};

const double INF = 1E18;
const double EPS = 1E-6;

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) {
	DSU dsu(N), dsu2(N);
	std::vector<std::pair<int, int>> adj[N];
	for(int i = 0; i < M; i++) {
		dsu.unite(x[i], y[i]);
		if(x[i] != H && y[i] != H) {
			dsu2.unite(x[i], y[i]);
		}

		adj[x[i]].emplace_back(y[i], c[i]);
		adj[y[i]].emplace_back(x[i], c[i]);
	}

	if(!dsu.same(0, H)) {
		return -1;
	}

	K = std::min(80, K);

	std::vector<double> pw(K + 1, 1);
	for(int i = 1; i <= K; i++) {
		pw[i] = pw[i - 1] / 2;
	}

	using T = std::tuple<double, int, int>;
	std::priority_queue<T, std::vector<T>, std::greater<T>> pq;
	pq.emplace(0, H, 0);

	std::vector dist(N, std::vector<double> (K + 1, -1));
	std::vector vis(N, std::vector<bool> (K + 1, false));
	double ans = INF;
	while(!pq.empty()) {
		auto [cost, node, bound] = pq.top();
		pq.pop();

		if(vis[node][bound]) {
			continue;
		}

		if(arr[node] == 0) {
			ans = std::min(ans, cost);
			break;
		}

		dist[node][bound] = cost;
		vis[node][bound] = true;

		for(auto [child, w] : adj[node]) {
			if(dsu2.same(0, child)) {
				pq.emplace(cost + w * pw[bound], child, bound);
				if(arr[node] == 2 && bound + 1 <= K) {
					pq.emplace(cost + w * pw[bound + 1], child, bound + 1);
				}
			}
		}
	}

	for(int i = 0; i <= K; i++) {
		if(vis[0][i]) {
			ans = std::min(ans, dist[0][i]);
		}
	}

	if(std::abs(ans - INF) <= EPS) {
		return -1;
	}

	return ans;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	856 KB	Correct.
2	Correct	22 ms	820 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	1872 KB	Correct.
2	Correct	41 ms	1876 KB	Correct.
3	Correct	34 ms	1884 KB	Correct.
4	Correct	34 ms	1872 KB	Correct.
5	Correct	35 ms	1880 KB	Correct.
6	Correct	36 ms	5596 KB	Correct.
7	Correct	39 ms	5476 KB	Correct.
8	Correct	25 ms	9820 KB	Correct.
9	Correct	33 ms	1420 KB	Correct.
10	Correct	33 ms	1360 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	1728 KB	Correct.
2	Correct	24 ms	1760 KB	Correct.
3	Correct	24 ms	1776 KB	Correct.
4	Correct	25 ms	1424 KB	Correct.
5	Correct	27 ms	1360 KB	Correct.
6	Correct	6 ms	4184 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	27916 KB	Correct.
2	Correct	27 ms	1872 KB	Correct.
3	Correct	25 ms	1920 KB	Correct.
4	Correct	27 ms	1904 KB	Correct.
5	Correct	30 ms	1360 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	1648 KB	Correct.
2	Correct	33 ms	2128 KB	Correct.
3	Correct	34 ms	1908 KB	Correct.
4	Correct	36 ms	5112 KB	Correct.
5	Correct	25 ms	1160 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	1772 KB	Correct.
2	Correct	20 ms	1692 KB	Correct.
3	Correct	41 ms	9640 KB	Correct.
4	Correct	14 ms	3664 KB	Correct.
5	Correct	24 ms	1368 KB	Correct.
6	Correct	23 ms	1704 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	1812 KB	Correct.
2	Correct	4 ms	856 KB	Correct.
3	Correct	69 ms	35604 KB	Correct.
4	Correct	55 ms	10660 KB	Correct.
5	Correct	51 ms	19808 KB	Correct.
6	Correct	33 ms	8784 KB	Correct.
7	Correct	51 ms	9760 KB	Correct.
8	Correct	51 ms	3200 KB	Correct.
9	Correct	21 ms	1724 KB	Correct.
10	Correct	22 ms	1532 KB	Correct.
11	Correct	54 ms	2280 KB	Correct.
12	Correct	29 ms	1592 KB	Correct.
13	Correct	25 ms	1548 KB	Correct.
14	Correct	57 ms	13392 KB	Correct.
15	Correct	50 ms	4932 KB	Correct.
16	Correct	23 ms	1476 KB	Correct.
17	Correct	26 ms	884 KB	Correct.
18	Correct	27 ms	796 KB	Correct.
19	Correct	51 ms	856 KB	Correct.
20	Correct	3 ms	344 KB	Correct.
21	Correct	2 ms	856 KB	Correct.
22	Correct	3 ms	1112 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	1140 KB	Correct.
2	Correct	4 ms	1112 KB	Correct.
3	Correct	1884 ms	84736 KB	Correct.
4	Correct	48 ms	5516 KB	Correct.
5	Correct	53 ms	33676 KB	Correct.
6	Correct	32 ms	13364 KB	Correct.
7	Correct	52 ms	16996 KB	Correct.
8	Correct	60 ms	3196 KB	Correct.
9	Correct	25 ms	2260 KB	Correct.
10	Correct	24 ms	1780 KB	Correct.
11	Correct	520 ms	1796 KB	Correct.
12	Correct	25 ms	2116 KB	Correct.
13	Correct	28 ms	2272 KB	Correct.
14	Correct	65 ms	34640 KB	Correct.
15	Correct	63 ms	43548 KB	Correct.
16	Correct	62 ms	14368 KB	Correct.
17	Correct	54 ms	5220 KB	Correct.
18	Correct	24 ms	2364 KB	Correct.
19	Correct	25 ms	2316 KB	Correct.
20	Correct	26 ms	2196 KB	Correct.
21	Correct	47 ms	3048 KB	Correct.
22	Correct	3 ms	600 KB	Correct.
23	Correct	3 ms	856 KB	Correct.
24	Correct	4 ms	1624 KB	Correct.

Submission #919224

Compilation message