Submission #1228042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228042		vako_p	Cyberland (APIO23_cyberland)	C++20	97 / 100	471 ms	44732 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define sd second

void dfs(int H, int at, vector<vector<pair<int,int>>>& v, vector<bool>& vis, vector<int>& arr, vector<int>& vv){
	if(vis[at]) return;
//	cout <<" ---> " << at << endl;
	vis[at] = true;
	if(at == H) return;
	if(!arr[at]) vv.pb(at);
	for(auto it1 : v[at]){
		int it = it1.ff;
		dfs(H, it, v, vis, arr, vv);
	}
}

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) {
	int n = N,m = M,k = K;
	vector<vector<pair<int,int>>> v(n);
	k = min(k, 30);
	for(int i = 0; i < m; i++){
		v[x[i]].pb({y[i], c[i]});
		v[y[i]].pb({x[i], c[i]});
	}
	priority_queue<pair<int,pair<double,int>>, vector<pair<int,pair<double,int>>>, greater<pair<int,pair<double,int>>>> q;
	vector<vector<double>> dis(35, vector<double>(n, 1e18));
	vector<bool> vis1(n, false);
	vector<vector<bool>> vis(35, vector<bool>(n, false));
	vector<int> vv;
	dfs(H, 0, v, vis1, arr, vv);
	if(!vis1[H]) return -1;
	for(int i = 0; i <= k; i++) dis[i][0] = 0;
	q.push({-k, {0, 0}});
	for(auto it : vv){
		for(int i = 0; i <= k; i++) dis[i][it] = 0;
		q.push({-k, {0, it}});
	}
	while(!q.empty()){
		int curr = -q.top().ff,at = q.top().sd.sd;
		q.pop();
		if(vis[curr][at] or at == H) continue;
		vis[curr][at] = true;
		double val = dis[curr][at];
		for(auto it1 : v[at]){
			int it = it1.ff;
			if(vis[curr][it]) continue;
			if(dis[curr][it] > val + it1.sd){
				dis[curr][it] = val + it1.sd;
				q.push({-curr, {dis[curr][it], it}});
			}
		}
		if(arr[at] == 2 and curr){
			curr--;
			val /= 2;
			for(auto it1 : v[at]){
				int it = it1.ff;
				if(vis[curr][it]) continue;
				if(dis[curr][it] > val + it1.sd){
					dis[curr][it] = val + it1.sd;
					q.push({-curr, {dis[curr][it], it}});
				}
			}
		} 
	}
	double ans = 1e18;
	for(int i = 0; i <= k; i++) ans = min(ans, dis[i][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: 0 / 3