Submission #960248

#	Time	Username	Problem	Language	Result	Execution time	Memory
960248		josanneo22	Cyberland (APIO23_cyberland)	C++17	100 / 100	325 ms	123612 KiB

cyberland

#include <bits/stdc++.h>
using namespace std;
 
struct dsu {
	vector<int> fa, sz;
	dsu(int n) {
		fa.resize(n + 10);
		iota(fa.begin(), fa.end(), 0);
		sz.assign(n + 10, 1);
	}
	int find(int x) {
		while (x != fa[x]) x = fa[x] = fa[fa[x]];
		return x;
	}
	bool merge(int x, int y) {
		int px = find(x), py = find(y);
		if (px == py) return false;
		if (sz[py] > sz[px]) swap(px, py);
		sz[px] += sz[py]; fa[py] = px;
		return true;
	}
	bool same(int x, int y) {
		int px = find(x), py = find(y);
		return px == py;
	}
};
 
 
#include "cyberland.h"
#define ld long double
double solve(int N, int M, int K, int H, vector<int> fir, vector<int> sec, vector<int> co, vector<int> arr) {
	K = min(K, 69);
	vector<vector<pair<int,int>>> g(N);
	dsu ds(N);
	for (int i = 0; i < M; i++) {
		if (fir[i] != H && sec[i] != H) ds.merge(fir[i], sec[i]); // merging
		g[fir[i]].push_back(make_pair(co[i], sec[i]));
		g[sec[i]].push_back(make_pair(co[i], fir[i])); // add the edges
	}
	vector<ld> pwr(K + 1, 1);
	// precompute the values (divided by) when getting powers of 2 
	for (int i = 1; i <= K; i++) {
		pwr[i] = pwr[i - 1] / 2; 
	}
	arr[0] = 0; // make node 0 with type 0 
	vector<vector<ld>> dist(K + 1, vector<ld>(N, 1E18));
	using node = tuple<ld, int, int>; // make a tuple of 3 numbers
	priority_queue<node, vector<node>, greater<node>> pq;
	auto enq = [&](int k, int x, ld d) { 
		// updates and push into queue if it is better
		if (dist[k][x] > d) { 
			dist[k][x] = d;
			pq.push({ d,k,x });
		}
	};
	enq(K, H, 0); // start from node H with K unused power 2 abilities
	while (pq.size()) {
		auto [d, k, x] = pq.top(); 
		pq.pop();
		if (dist[k][x] < d) continue;
		if (arr[x] == 0) return (double)d; 
		// if we reach a node with type 0
		// means that we can always go from node 0 -> x -> H
		// with the use of Dijkstra, we know that our first encounter is the shortest time
		for (auto& [c, v] : g[x]) {
			if (ds.find(v) != ds.find(0)) continue; // if not connected with node 0
			enq(k, v, d + c * pwr[K - k]); // don't use power 2
			if (arr[x] == 2 && k > 0) // if we have remaining and current node has type 2 
				enq(k - 1, v, d + c * pwr[K - k + 1]); // use power 2
		}
	}
	return (double)-1; // returns impossible
}

• 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: 3 / 3