Submission #748992

#	Time	Username	Problem	Language	Result	Execution time	Memory
748992		penguin133	Cyberland (APIO23_cyberland)	C++17	100 / 100	1069 ms	64392 KiB

cyberland

#include <bits/stdc++.h>
using namespace std;
 
#include "cyberland.h"
typedef long double ld;
typedef long long ll;
#define fi first
#define se second
#define pi pair<int, int>
#define pii pair<int, pi>
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
vector <pi> adj[100000];
double dist[75][100000];
 
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) {
	K = min(K, 70);
    priority_queue <pair<double, int>, vector<pair<double, int> >, greater<pair<double, int> > > pq;
    for(int i=0;i<N;i++)for(int j=0;j<=K;j++)dist[j][i] = 1e18;
    dist[0][0] = 0;
    for(int i=0;i<N;i++)adj[i].clear();
    for(int i=0;i<M;i++){
		adj[x[i]].push_back({y[i], c[i]});
		adj[y[i]].push_back({x[i], c[i]});
	}
	for(int i = 0; i <= K; i++){
		for(int j = 0; j < N; j++){
			if(dist[i][j] != 1e18)pq.push({dist[i][j], j});
		}
		while(!pq.empty()){
			double a = pq.top().fi; int b = pq.top().se;
			pq.pop();
			if(dist[i][b] < a || b == H)continue;
			for(auto [ii, j] : adj[b]){
				
				if(arr[ii] == 0){
					if(dist[i][ii])dist[i][ii] = 0, pq.push({0, ii});
				}
				else if(dist[i][ii] > a + j)dist[i][ii] = a + j, pq.push({dist[i][ii], ii});
				if(arr[ii] == 2 && i < K){
					if(dist[i+1][ii] > (a + ((double)j)) / 2)dist[i+1][ii] = (a + ((double)j)) / 2;
				}
			}
		}
	}
	
	double ans = 1e18;
	for(int i=0;i<=K;i++)ans = min(ans, dist[i][H]);
	if(ans > 1e15)return -1;
	else 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