Submission #982074

#	Time	Username	Problem	Language	Result	Execution time	Memory
982074		vjudge1	Cyberland (APIO23_cyberland)	C++17	44 / 100	38 ms	13908 KiB

cyberland

#include "cyberland.h"

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

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

double solveNoTwos(int N, int M, int K, int H, vector<vector<pll>> G,
                   vector<int> arr) {
	vector<bool> v(N);
	priority_queue<pair<double, ll>, vector<pair<double, ll>>,
	               greater<pair<double, ll>>>
	  q;
	arr[0] = 0;

	{
		vector<bool> v(N);
		queue<ll>    qt;
		qt.push(0);
		while (qt.size()) {
			ll node = qt.front();
			qt.pop();
			if (v[node] || node == H) continue;
			v[node] = true;
			if (!arr[node]) q.push({0, node});
			for (pll& nei : G[node]) qt.push(nei.first);
		}
	}

	double ans = LLONG_MAX;
	while (q.size()) {
		ll     node = q.top().second;
		double c    = q.top().first;
		q.pop();
		if (node == H) ans = min(ans, c);
		if (v[node] || node == H) continue;
		v[node] = true;
		for (pll& nei : G[node]) q.push({nei.second + c, nei.first});
	}

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

double solve3(int N, int M, int K, int H, vector<vector<pll>> G,
              vector<int> arr) {
	double                            ans = LLONG_MAX;
	queue<pair<pair<ll, ll>, double>> q;
	vector<bool>                      v(N);
	q.push({{0, -1}, 0});

	while (q.size()) {
		ll     node = q.front().first.first;
		ll     p    = q.front().first.second;
		double c    = q.front().second;
		q.pop();

		if (arr[node] == 2) c /= 2;
		if (arr[node] == 0) c = 0;

		if (node == H) ans = min(ans, c);
		if (v[node] || node == H) continue;
		v[node] = true;

		for (pll& nei : G[node])
			if (nei.first != p && !v[nei.first])
				q.push({{nei.first, node}, nei.second + c});
	}

	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) {
	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]});
	}
	if (arr[H] == 0) return 0;
	if (N == 2 || (G[0].size() == 1 && G[0][0].first == H)) {
		if (!M) return -1;
		if (arr[H] == 2) return G[0][0].second / double(2);
		return G[0][0].second;
	}
	if (N == 3) return solve3(N, M, K, H, G, arr);

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

	if (NoTwos) return solveNoTwos(N, M, K, H, G, arr);
	return -1;
}

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