Submission #1200296

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200296		crispxx	Cyberland (APIO23_cyberland)	C++20	68 / 100	1000 ms	2162688 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'

// #include "stub.cpp"

struct DSU {
	int n; vector<int> p, sz;
	DSU(int n) : p(n), sz(n, 1) {
		iota(all(p), 0);
	}
	int find(int v) {
		return v == p[v] ? v : p[v] = find(p[v]);
	}
	bool unite(int u, int v) {
		u = find(u), v = find(v);
		if(u == v) return false;
		if(sz[u] < sz[v]) swap(u, v);
		p[v] = u;
		sz[u] += sz[v];
		return true;
	}
};

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> a) {
	vector<vector<ar<int, 2>>> adj(n);
	DSU dsu(n);
	for(int i = 0; i < m; i++) {
		adj[x[i]].pb({y[i], c[i]});
		adj[y[i]].pb({x[i], c[i]});
		if(x[i] != h && y[i] != h) {
			dsu.unite(x[i], y[i]);
		}
	}
	
	vector d(n, vector<long double>(k + 1, 1e18));
	
	priority_queue<pair<long double, int>, vector<pair<long double, int>>, greater<>> pq;
	pq.emplace(d[0][0] = 0, 0);
	
	for(int i = 0; i < n; i++) {
		if(a[i] == 0 && dsu.find(0) == dsu.find(i)) {
			pq.emplace(d[i][0] = 0, i);
		}
	}
	
	int K = k;
	
	long double ans = 1e18;
	
	for(int i = 0; i < K; i++) {
		k = i;
		priority_queue<pair<long double, int>, vector<pair<long double, int>>, greater<>> nxt;
		while(!pq.empty()) {
			auto [d_v, v] = pq.top();
			pq.pop();
			if(d_v != d[v][k]) continue;
			if(v == h) {
				ans = min(ans, d[v][k]);
				continue;
			}
			for(auto [to, c] : adj[v]) {
				if(d[to][k] > d[v][k] + c) {
					pq.emplace(d[to][k] = d[v][k] + c, to);
				}
				if(a[to] == 2 && d[to][k + 1] > (d[v][k] + c) / 2) {
					nxt.emplace(d[to][k + 1] = (d[v][k] + c) / 2, to);
				}
			}
		}
		swap(pq, nxt);
	}
	
	return ans == 1e18 ? -1 : 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: 0 / 29
• Subtask 8: 0 / 3