Submission #831606

#	Time	Username	Problem	Language	Result	Execution time	Memory
831606		pavement	Cyberland (APIO23_cyberland)	C++17	97 / 100	3063 ms	107868 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using ld = long double;
using diii = tuple<ld, int, int, bool>;

#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define ppb pop_back

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
	K = min(K, 1000);
	bool vis[N];
	ld dist[N][K + 1][2];
	vector<ii> adj[N];
	queue<int> Q;
	priority_queue<diii, vector<diii>, greater<diii> > pq;
	for (int i = 0; i < N; i++) {
		vis[i] = 0;
		for (int j = 0; j <= K; j++) {
			dist[i][j][0] = dist[i][j][1] = (ld)1e18;
		}
	}
	for (int i = 0; i < M; i++) {
		adj[x[i]].eb(y[i], c[i]);
		adj[y[i]].eb(x[i], c[i]);
	}
	vis[0] = 1;
	Q.push(0);
	while (!Q.empty()) {
		int v = Q.front();
		Q.pop();
		for (auto [u, w] : adj[v]) {
			if (!vis[u] && u != H) {
				vis[u] = 1;
				Q.push(u);
			}
		}
	}
	for (int i = 0; i < N; i++) {
		if (vis[i] && (arr[i] == 0 || i == 0)) {
			dist[i][K][0] = dist[i][K][1] = 0;
			pq.emplace(0, i, K, 0);
		}
	}
	while (!pq.empty()) {
		auto [d, v, k, jd] = pq.top();
		pq.pop();
		if (d != dist[v][k][jd]) continue;
		if (v == H) continue;
		if (arr[v] == 2 && k && !jd) {
			if (d / (ld)2 < dist[v][k - 1][1]) {
				dist[v][k - 1][1] = d / (ld)2;
				pq.emplace(dist[v][k - 1][1], v, k - 1, 1);
			}
		}
		for (auto [u, w] : adj[v]) {
			if (d + w < dist[u][k][0]) {
				dist[u][k][0] = d + w;
				pq.emplace(dist[u][k][0], u, k, 0);
			}
		}
	}
	ld ret = min(dist[H][0][0], dist[H][0][1]);
	for (int i = 1; i <= K; i++) ret = min({ret, dist[H][i][0], dist[H][i][1]});
	return ret == (ld)1e18 ? -1 : ret;
}

• 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