Submission #749417

#	Time	Username	Problem	Language	Result	Execution time	Memory
749417		Batorgil952	Cyberland (APIO23_cyberland)	C++17	97 / 100	3046 ms	128684 KiB

cyberland

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second

using namespace std;

const ll N=100005;
vector< pair< ll, ll > > v[N];
double T[N][71];
bool B[N];
ll Ra[N];

void DFS(ll s, ll f){
	Ra[s]=1;
	if(s==f) return;
	ll vn=v[s].size();
	for(int i=0; i<vn; i++){
		if(!B[v[s][i].ff]){
			B[v[s][i].ff]=true;
			DFS(v[s][i].ff, f);
		}
	}
	return;
}

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);
	for(ll i=0; i<N; i++){
		Ra[i]=0;
		B[i]=false;
		v[i].clear();
	}
	for(ll i=0; i<M; i++){
		ll X=x[i], Y=y[i], Z=c[i];
		v[X].pb(mp(Y, Z));
		v[Y].pb(mp(X, Z));
	}
	
	Ra[0]=1;
	B[0]=true;
	DFS(0, H);
	if(!Ra[H]) return -1;
	priority_queue< pair< double, pair< ll, ll > >, vector< pair< double, pair< ll, ll > > >, greater< pair< double, pair< ll, ll > > > > q;
	
	for(ll i=0; i<N; i++){
		if(Ra[i] && !arr[i]){
			q.push(mp(0.0, mp(0, i)));
			for(ll j=0; j<=70; j++){
				T[i][j]=0.0;
			}
		}
		else if(i==0){
			q.push(mp(0.0, mp(0, i)));
			for(ll j=0; j<=70; j++){
				T[i][j]=0.0;
			}
		}
		else{
			for(ll j=0; j<=70; j++){
				T[i][j]=1000000000000000000.0;
			}
		}
	}
	
	while(!q.empty()){
		double fx=q.top().ff;
		ll fy=q.top().ss.ff;
		ll fz=q.top().ss.ss;
		q.pop();
		if(T[fz][fy]<fx){
			continue;
		}
		if(fz==H){
			continue;
		}
		ll vn=v[fz].size();
		for(ll i=0; i<vn; i++){
			double dd=v[fz][i].ss*1.0;
			double fare=fx+dd;
			if(arr[v[fz][i].ff]==1){
				if(fare<T[v[fz][i].ff][fy]){
					q.push(mp(fare, mp(fy, v[fz][i].ff)));
					T[v[fz][i].ff][fy]=fare;
				}
			}
			if(arr[v[fz][i].ff]==2){
				if(fare<T[v[fz][i].ff][fy]){
					q.push(mp(fare, mp(fy, v[fz][i].ff)));
					T[v[fz][i].ff][fy]=fare;
				}
				if(fy+1<=K && fare/2.0<T[v[fz][i].ff][fy+1]){
					fare/=2.0;
					q.push(mp(fare, mp(fy+1, v[fz][i].ff)));
					T[v[fz][i].ff][fy+1]=fare;
				}
			}
		}
	}
	
	double ans=1000000000000000000.0;
	for(ll i=0; i<=K; i++){
		ans=min(ans, T[H][i]);
	}
	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