Submission #1179788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179788		Dedibeat	Cyberland (APIO23_cyberland)	C++20	0 / 100	20 ms	8316 KiB

cyberland

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using node = pair<double, int>;

vector<vector<node>> adj;
vector<int> reach;
int dest;
void dfs(int v)
{
	reach[v] = 1;
	for(auto [u, w] : adj[v])
	{
		if(!reach[u] && u != dest) dfs(u);
	}
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> a) 
{
	K = min(K, 30);
	adj.assign(N, {});
	reach.assign(N, 0);
	for(int i = 0; i < M; i++)
	{
		adj[x[i]].emplace_back(y[i], c[i]);
		adj[y[i]].emplace_back(x[i], c[i]);
	}
	
	dest = H;
	dfs(0);
	
	priority_queue<node, vector<node>, greater<>> q;
	vector<double> dist(N, 1e18);
	
	for(int i = 0; i < N; i++)
	{
		if(a[i] == 0 && reach[i]) dist[i] = 0, q.emplace(0, i);
	}
	
	double ans = 1e18;
	q.emplace(0, 0);
	while(K--)
	{
		priority_queue<node, vector<node>, greater<>> next_q;
		vector<double> next_dist(N, 1e18);
		while(q.empty())
		{
			auto [c, v] = q.top(); q.pop();
			if(abs(c - dist[v]) > 1e-9) continue;
			if(v == H) ans = min(ans, c);
			for(auto [u, w] : adj[v])
			{
				if(c + w < dist[u])
				{
					dist[u] = c + w;
					q.emplace(c + w, u);
				}
			}
			
			if(a[v] == 2 && c < 2 * next_dist[v])
			{
				next_dist[v] = c / 2;
				next_q.emplace(c / 2, v);
			}
			
		}
		dist = next_dist;
		q = next_q;
	}
	
	if(ans < 1e18) return ans;
	else return -1;
	
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3