Submission #749643

#	Time	Username	Problem	Language	Result	Execution time	Memory
749643		happypotato	Cyberland (APIO23_cyberland)	C++17	97 / 100	3070 ms	225664 KiB

cyberland

#include "cyberland.h"

#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define ld long double
#pragma GCC optimize("Ofast")

const int mxN = 1e5 + 1;
vector<pii> adj[mxN];
short special[mxN];
int n, k, h;

bool cango[mxN];

void FindConnected() {
	queue<int> q;
	q.push(0); cango[0] = true;
	while (!q.empty()) {
		int cur = q.front(); q.pop();
		if (cur == h) continue;
		for (pii &v : adj[cur]) {
			if (!cango[v.ff]) {
				q.push(v.ff);
				cango[v.ff] = true;
			}
		}
	}
}

const int mxK = 70;
double dist[mxN][mxK];
priority_queue<pair<double, pii>, vector<pair<double, pii>>, greater<pair<double, pii>>> pq;
const double INF = 1e18, EPS = 1e-8;
void FindAnswer() {
	while (!pq.empty()) pq.pop();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= min(k, mxK - 1); j++) {
			dist[i][j] = INF;
		}
	}
	dist[0][0] = 0;
	pq.push({0, {0, 0}});
	for (int i = 0; i < n; i++) {
		if (cango[i] && special[i] == 0) {
			dist[i][0] = 0;
			pq.push({0, {i, 0}});
		}
	}
	while (!pq.empty()) {
		pair<double, pii> cur = pq.top();
		pq.pop();
		// if (cur.ss.ss <= 3) {
		// 	cerr << "DIJK " << cur.ff << ' ' << cur.ss.ff << ' ' << cur.ss.ss << endl;
		// }
		if (cur.ff > dist[cur.ss.ff][cur.ss.ss]) continue;
		if (cur.ss.ff == h) continue;
		double ncur;
		for (pii &v : adj[cur.ss.ff]) {
			ncur = cur.ff + v.ss;
			if (ncur < dist[v.ff][cur.ss.ss]) {
				dist[v.ff][cur.ss.ss] = ncur;
				pq.push({ncur, {v.ff, cur.ss.ss}});
			}
			if (special[v.ff] == 2 && cur.ss.ss + 1 < mxK) {
				ncur /= 2;
				if (ncur < dist[v.ff][cur.ss.ss + 1]) {
					dist[v.ff][cur.ss.ss + 1] = ncur;
					pq.push({ncur, {v.ff, cur.ss.ss + 1}});
				}
			}
		}
	}
}

double solve(int N, int M, int K, int H, vector<int> X, vector<int> Y, vector<int> C, vector<int> arr) {
	n = N; k = K; h = H;
	for (int i = 0; i < n; i++) {
		adj[i].clear();
		cango[i] = false;
	}
	for (int i = 0; i < M; i++) {
		adj[X[i]].pb({Y[i], C[i]});
		adj[Y[i]].pb({X[i], C[i]});
	}
	for (int i = 0; i < n; i++) {
		special[i] = arr[i];
	}
	// assert(special[0] == 1 && special[h] == 1);

	FindConnected();
	if (!cango[h]) return -1;

	// cerr << setprecision(1) << fixed;
	FindAnswer();
	// cerr << "DEBUG:\n";
	// for (int i = 0; i < n; i++) {
	// 	cerr << "NODE " << i << ": ";
	// 	for (int j = 0; j < 3; j++) cerr << dist[i][j] << ' ';
	// 	cerr << endl;
	// }
	double res = 1e18;
	for (int i = 0; i <= min(k, mxK - 1); i++) {
		res = min(res, dist[h][i]);
	}
	return res;
}

• 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