Submission #759229

#	Time	Username	Problem	Language	Result	Execution time	Memory
759229		ymm	Cyberland (APIO23_cyberland)	C++17	100 / 100	1679 ms	14240 KiB

cyberland

#include "cyberland.h"

#include <bits/stdc++.h>
#define Loop(x, l, r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

const double inf = 1e100;
const int N = 100'010;
vector<pii> A[N];
int n;

vector<double> dij(vector<double> dis, int dst)
{
	priority_queue<pair<double,int>, vector<pair<double,int>>, greater<pair<double,int>>> Q;
	Loop (i,0,n)
		Q.push({dis[i], i});
	while (Q.size()) {
		auto [d, v] = Q.top();
		Q.pop();
		if (d != dis[v])
			continue;
		if (v == dst)
			continue;
		for (auto [u, w] : A[v]) {
			if (d + w >= dis[u])
				continue;
			dis[u] = d + w;
			Q.push({dis[u], u});
		}
	}
	return dis;
}

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) {
	n = N;
	Loop (i,0,n)
		A[i].clear();
	Loop (i,0,M) {
		int v = x[i], u = y[i], w = c[i];
		A[v].push_back({u, w});
		A[u].push_back({v, w});
	}
	vector<double> dis(n, inf);
	dis[0] = 0;
	dis = dij(dis, H);
	if (dis[H] == inf)
		return -1;
	Loop (i,0,n)
		dis[i] = dis[i] != inf && arr[i] == 0? 0: inf;
	dis[0] = 0;
	double ans = inf;
	Loop (_,0,min(K+1,90)) {
		dis = dij(dis, H);
		ans = min(ans, dis[H]);
		vector<double> dis2(n, inf);
		Loop (v,0,n) {
			if (arr[v] != 2)
				continue;
			for (auto [u, w] : A[v])
				dis2[u] = min(dis2[u], dis[v]/2 + w);
		}
		dis = dis2;
	}
	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