Submission #982006

#	Time	Username	Problem	Language	Result	Execution time	Memory
982006		vjudge1	Cyberland (APIO23_cyberland)	C++17	0 / 100	2804 ms	2097152 KiB

cyberland

#include "cyberland.h"

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

using ll  = long long;
using pll = pair<ll, ll>;

double solve1(int N, int M, int K, int H, vector<vector<pll>> g,
              std::vector<int> arr) {
	struct state {
		ll     usedK  = 0;
		ll     passed = 0;
		ll     node   = 0;
		double time   = 0;
	};

	double       ans = INT_MAX;
	queue<state> q;
	q.push({0, 0, 0, 0});

	while (q.size()) {
		state now = q.front();
		q.pop();

		if (now.passed > 50 || now.usedK > K) continue;
		if (now.node == H) {
			if (arr[now.node] == 2 && now.usedK < K) now.time /= 2;
			ans = min(now.time, ans);
			continue;
		}

		for (pll& nei : g[now.node]) {
			state newState = {now.usedK, now.passed + 1, nei.first,
			                  now.time + nei.second};

			if (arr[nei.first] == 0) newState.time = 0;
			q.push(newState);

			if (arr[nei.first] == 2 && newState.usedK < K) {
				newState.usedK++;
				newState.time /= 2;
				q.push(newState);
			}
		}
	}

	if (ans == INT_MAX) return -1;
	return ans;
}

double solve2(int N, int M, int K, int H, vector<vector<pll>> g,
              std::vector<int> arr) {
	priority_queue<pair<double, ll>, vector<pair<double, ll>>,
	               greater<pair<double, ll>>>
	       q;
	double ans = INT_MAX;

	q.push({0, 0});
	vector<bool> vis(N);
	while (q.size()) {
		ll     node = q.top().second;
		double cost = q.top().first;
		q.pop();

		if (node == H) {
			ans = min(cost, ans);
			continue;
		}
		if (vis[node]) continue;
		vis[node] = true;
		for (pll& nei : g[node])
			if (!vis[nei.first])
				q.push({nei.second + cost, nei.first});
	}

	if (ans == INT_MAX) return -1;
	return ans;
}

double solve3(int N, int M, int K, int H, vector<vector<pll>> g,
              std::vector<int> arr) {
	priority_queue<pair<double, ll>, vector<pair<double, ll>>,
	               greater<pair<double, ll>>>
	       q;
	double ans = INT_MAX;

	q.push({0, H});
	vector<bool> vis(N), reach(N);

	{
		queue<ll> qt;
		qt.push(0);
		while (qt.size()) {
			ll node = qt.front();
			qt.pop();
			if (reach[node]) continue;
			reach[node] = true;

			for (pll& nei : g[node])
				if (!reach[nei.first]) qt.push(nei.first);
		}
	}

	while (q.size()) {
		ll     node = q.top().second;
		double cost = q.top().first;
		q.pop();

		if (arr[node] == 0 && reach[node]) {
			ans = cost;
			break;
		}

		if (vis[node]) continue;
		vis[node] = true;
		for (pll& nei : g[node])
			if (!vis[nei.first])
				q.push({nei.second + cost, nei.first});
	}

	if (ans == INT_MAX) return -1;
	return ans;
}

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) {
	if (arr[H] == 0) return 0;

	vector<vector<pll>> G(N);
	for (int i = 0; i < M; i++) {
		G[x[i]].push_back({y[i], c[i]});
		G[y[i]].push_back({x[i], c[i]});
	}

	bool allOnes = 1;
	for (int& i : arr)
		if (i != 1) {
			allOnes = 0;
			break;
		}

	if (N <= 3) return solve1(N, M, K, H, G, arr);
	if (allOnes) return solve2(N, M, K, H, G, arr);
	return solve3(N, M, K, H, G, arr);
}

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