Submission #748999

#	Time	Username	Problem	Language	Result	Execution time	Memory
748999		emptypringlescan	Cyberland (APIO23_cyberland)	C++17	97 / 100	2429 ms	321012 KiB

cyberland

#include <bits/stdc++.h>
using namespace std;

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){
	vector<pair<int,long double> > adj[N];
	int n=N,m=M,k=K,h=H;
	int sz=64;
	k=min(k,sz-1);
	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]});
	}
	int can[n];
	memset(can,0,sizeof(can));
	queue<int> q;
	q.push(0);
	while(!q.empty()){
		int a=q.front();
		q.pop();
		if(can[a]) continue;
		can[a]=1;
		for(auto i:adj[a]){
			if(!can[i.first]&&i.first!=h) q.push(i.first);
			if(i.first==h) can[h]=1;
		}
	}
	if(!can[h]) return -1;
	long double dist[k+5][n];
	for(int j=0; j<k+5; j++) for(int i=0; i<n; i++) dist[j][i]=1e16;
	priority_queue<pair<long double,int>,vector<pair<long double,int>>,greater<pair<long double,int> > > pq[k+5];
	pq[0].push({0,0});
	for(int i=1; i<n; i++){
		if(arr[i]==0&&can[i]){
			pq[0].push({0,i});
		}
	}
	for(int i=0; i<=k; i++){
		if(i){
			for(int j=0; j<n; j++) dist[i][j]=min(dist[i][j],dist[i-1][j]);
			for(int j=0; j<n; j++) if(can[j]) pq[i].push({dist[i][j],j});
		}
		while(!pq[i].empty()){
			long double a=pq[i].top().first;
			int b=pq[i].top().second;
			pq[i].pop();
			if(dist[i][b]<a) continue;
			dist[i][b]=a;
			if(b==h) continue;
			long double cc=a/(long double)2.0;
			for(auto j:adj[b]){
				if(dist[i][j.first]>a+j.second){
					pq[i].push({a+j.second,j.first});
				}
				if(i<k&&arr[b]==2){
					if(dist[i+1][j.first]>cc+j.second){
						dist[i+1][j.first]=cc+j.second;
					}
				}
			}
		}
	}
	return (double)dist[k][h];
}/*
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout << solve(3,3,1,2,{0,0,1},{1,2,2},{10000,500000,1},{1,2,1});
}*/

• 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