Submission #804494

#	Time	Username	Problem	Language	Result	Execution time	Memory
804494		MadokaMagicaFan	Cyberland (APIO23_cyberland)	C++17	100 / 100	747 ms	20048 KiB

cyberland

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
#define sz(v) ((int)(v).size())
#define pb push_back

const int N = 1e5;
vector<array<ll, 2>> adj[N];
bitset<N> v, ps;
ll mind1[N], mind2[N], sme[N];
ld md[N];
ll inf = 1e18;

void
dfs(int x, int h) {
	if (x == h) return;
	if (ps[x]) return;
	ps[x] = 1;

	for (auto u : adj[x])
		dfs(u[0], h);
}

double
solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr)
{
	for (int i = 0; i < n; ++i) {
		sme[i] = inf;
		mind2[i] = inf;
		mind1[i] = 0;
		while (sz(adj[i]))
			adj[i].pop_back();
	}
	v = 0;
	ps = 0;

	if (h == 0) return 0;
	for (int i = 0; i < m; ++i) {
		adj[x[i]].pb({y[i], c[i]});
		if (y[i] != h)
			sme[x[i]] = min(sme[x[i]], (ll)c[i]);
		adj[y[i]].pb({x[i], c[i]});
		if (x[i] != h)
			sme[y[i]] = min(sme[y[i]], (ll)c[i]);
	}

	dfs(0, h);
	priority_queue<array<ll, 2>> q;
	for (int i = 1; i < n; ++i) {
		if (arr[i] == 0 && ps[i]) {
			q.push({0, i});
			mind1[i] = 0;
		}
		else
			mind1[i] = inf;
	}
	q.push({0, 0});

	while (sz(q)) {
		auto u = q.top();
		q.pop();
		if (v[u[1]]) continue;
		if (u[1] == h) continue;
		v[u[1]] = 1;

		for (auto x : adj[u[1]]) {
			if (mind1[u[1]]+ x[1] < mind1[x[0]]) {
				mind1[x[0]] = mind1[u[1]]+ x[1];
				q.push({-mind1[x[0]], x[0]});
			}
		}
	}

	if (mind1[h] > 1e17) return -1;

	long double ans = mind1[h];
	while (sz(q)) q.pop();
	mind2[h] = 0;
	q.push({0, h});

	v = 0;
	while (sz(q)) {
		auto u = q.top();
		q.pop();
		if (v[u[1]]) continue;
		v[u[1]] = 1;

		for (auto x : adj[u[1]]) {
			if (mind2[u[1]]+ x[1] < mind2[x[0]]) {
				mind2[x[0]] = mind2[u[1]]+ x[1];
				q.push({-mind2[x[0]], x[0]});
			}
		}
	}

	int cn = min(k, 200);
	for (int i = 0; i < n; ++i) {
		md[i] = mind1[i];
	}
	priority_queue<pair<ld, int>> qq;
	while (cn--) {
		while (sz(qq)) qq.pop();
		v = 0;
		for (int i = 1; i < n; ++i) {
			if (arr[i] == 2 && ps[i]) {
				qq.push({-(md[i] / ((ld) 2)), i});
			}
		}

		while (sz(qq)) {
			auto u = qq.top();
			qq.pop();
			if (v[u.second]) continue;
			if (u.second == h) continue;
			v[u.second] = 1;

			for (auto x : adj[u.second]) {
				if (-u.first + ((ld)x[1]) < md[x[0]]) {
					md[x[0]] = -u.first + ((ld)x[1]);
					qq.push({-md[x[0]], x[0]});
				}
			}
		}

		ans = min(ans, md[h]);
	}

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