Submission #1088948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088948		Math4Life2020	Cyberland (APIO23_cyberland)	C++17	42 / 100	3060 ms	2097152 KiB

cyberland

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
using ld = long double; using vi = vector<int>;

const ld INF = 1e18;

double solve(int N, int M, int K, int H, vi x, vi y, vi c, vi arr) {
	ld tmin[N][K+1];
	bool dfsf[N];
	for (ll i=0;i<N;i++) {
		dfsf[i]=0;
		for (ll k=0;k<=K;k++) {
			tmin[i][k]=INF;
		}
	}
	vector<pii> adj[N]; //vertex,cost
	for (ll i=0;i<M;i++) {
		adj[x[i]].push_back({y[i],c[i]});
		adj[y[i]].push_back({x[i],c[i]});
	}
	stack<int> s;
	s.push(0);
	while (!s.empty()) {
		ll x0 = s.top(); s.pop();
		if (!dfsf[x0]) {
			dfsf[x0]=1;
			if (x0==H) {
				continue;
			}
			for (pii p0: adj[x0]) {
				s.push(p0.first);
			}
		}
	}
	if (!dfsf[H]) {
		return -1.0;
	}
	priority_queue<pair<ll,pair<ld,ll>>> pq; //{#k,{time,position}}
	pq.push({0,{0.0,0}});
	for (ll i=0;i<N;i++) {
		if (dfsf[i] && (arr[i]==0)) {
			pq.push({0,{0.0,i}});
		}
	}
	while (!pq.empty()) {
		auto A = pq.top(); pq.pop();
		ld T = A.second.first; ll x0 = A.second.second; ll k = A.first;
		if (arr[x0]==0 && T != 0.0) {
			continue;
		}
		if (tmin[x0][k]<=(T+1e-10)) {
			continue;
		}
		tmin[x0][k]=min(tmin[x0][k],T);
		if (x0==H) {
			continue;
		}
		for (pii p0: adj[x0]) {
			ll y0 = p0.first; ld ce = p0.second;
			pq.push({k,{ce+T,y0}});
			if (arr[x0]==2 && k<K) {
				pq.push({k+1,{ce+T/2,y0}});
			}
		}
	}
	ld ans = INF;
	for (ll k=0;k<=K;k++) {
		ans = min(ans,tmin[H][k]);
	}
	return ans;
}

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