Submission #878664

#	Time	Username	Problem	Language	Result	Execution time	Memory
878664		hello_there_123	Cyberland (APIO23_cyberland)	C++17	15 / 100	3204 ms	2018408 KiB

cyberland

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#include "cyberland.h"

double solve(int N, int M, int K, int end, std::vector<int> x, std::vector<int> y, std::vector<int> z, std::vector<int> arr) {
 	vector<pair<int,int> >v[N+3];  //node, val 
	for(int i=0;i<M;i++){
		v[x[i]].push_back(make_pair(y[i],z[i]));
		v[y[i]].push_back(make_pair(x[i],z[i]));
	}
	priority_queue<pair<double, pair<int,int> >, vector<pair<double,pair<int,int> > >, greater<pair<double,pair<int,int> > > > pq;
	//val, node, k
	double dist[N+3][K+3];
	bool vis[N+3];
	memset(vis,0,sizeof(vis));
	queue<int>q;
	q.push(0);
	vis[0] = 1;
	while(!q.empty()){
		int no = q.front();
		q.pop();
		for(auto p:v[no]){
			if(!vis[p.first])q.push(p.first);
			vis[p.first] = 1;
		}
	}
	for(int i=0;i<N;i++){
		if(vis[i] == 1 && (arr[i] == 0 || i==0)){
			for(int j=0;j<=K;j++){
				dist[i][j] = 0;
				pq.push(mp(0,mp(i,j)));
			}
		}
		else for(int j=0;j<=K;j++) dist[i][j] = -1;
	}
	while(!pq.empty()){
		double val = pq.top().first;
		int no = pq.top().second.first;
		int k = pq.top().second.second;
		pq.pop();
		if(no == end) continue;
		for(auto p: v[no]){
			if(dist[p.first][k] == -1 || dist[p.first][k] > val + (double) p.second){
				
				dist[p.first][k] = val+(double)p.second;
				pq.push(mp(val+(double)p.second,mp(p.first,k)));
			}/*
			if(k == K || arr[p.first]!=2) continue;
			if(dist[p.first][k+1] == -1 || dist[p.first][k+1] > (val+(double)p.second)/2){
				dist[p.first][k+1] = (val+(double)p.second)/2;
				pq.push(mp((val+(double)p.second)/2, mp(p.first,k+1)));
			}*/
		}
	}
	double ans = 1e15;
	for(int i=0;i<=K;i++){
		if(dist[end][i]!=-1) ans = min(ans, dist[end][i]);
	}
	if(vis[end] == 0) return -1;
	assert(ans!=1e15);
	 return ans;
}

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