Submission #919218

#	Time	Username	Problem	Language	Result	Execution time	Memory
919218		MisterReaper	Cyberland (APIO23_cyberland)	C++17	97 / 100	3039 ms	106036 KiB

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(100, 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);
		}

		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 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 29 / 29
• Subtask 8: 0 / 3