Submission #748978

#	Time	Username	Problem	Language	Result	Execution time	Memory
748978		penguin133	Cyberland (APIO23_cyberland)	C++17	97 / 100	3036 ms	92564 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[69][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, 68);
    priority_queue <pair<double, pi>, vector<pair<double, pi> >, greater<pair<double, pi> > > pq;
    pq.push({0.0, {0, 0}});
    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]});
	}
	while(!pq.empty()){
		double a = pq.top().fi; int b = pq.top().se.fi, c = pq.top().se.se;
		pq.pop();
		if(dist[c][b] < a || b == H)continue;
		for(auto [i, j] : adj[b]){
			
			if(arr[i] == 0){
				if(dist[c][i])dist[c][i] = 0, pq.push({0, {i, c}});
			}
			else if(dist[c][i] > a + j)dist[c][i] = a + j, pq.push({dist[c][i], {i, c}});
			if(arr[i] == 2 && c < K){
				if(dist[c+1][i] > (a + ((double)j)) / 2)dist[c+1][i] = (a + ((double)j)) / 2, pq.push({dist[c+1][i], {i, c+1}});
			}
		}
	}
	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: 0 / 3