Submission #975650

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
975650	2024-05-05T16:01:17 Z	vjudge1	Cyberland (APIO23_cyberland)	C++17	100 / 100	1377 ms	69336 KB

cyberland

#include "cyberland.h"

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

#define F first
#define S second

const double INF = 1e18 + 7;

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr)
{
	K = min(K, 70);
	vector<vector<pair<int, double>>> adj(N);
	for (int i = 0; i < M; i++)
	{
		adj[x[i]].emplace_back(y[i], c[i]);
		adj[y[i]].emplace_back(x[i], c[i]);
	}

	vector<bool> vis(N);
	queue<int> Q;
	Q.push(0);
	while (!Q.empty())
	{
		int u = Q.front();
		Q.pop();

		if (u == H)
			continue;

		for (pair<int, double> i : adj[u])
			if (!vis[i.F])
			{
				vis[i.F] = 1;
				Q.push(i.F);
			}
	}

	priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> PQ;
	vector<vector<double>> dist(N, vector<double>(K + 1, INF));
	for (int i = 0; i < N; i++)
		if (vis[i] && arr[i] == 0)
		{
			dist[i][0] = 0;
			PQ.emplace(0, i);
		}

	dist[0][0] = 0;
	PQ.emplace(0, 0);
	while (!PQ.empty())
	{
		double d;
		int u;
		tie(d, u) = PQ.top();
		PQ.pop();

		if (d != dist[u][0] || u == H)
			continue;

		for (pair<int, double> i : adj[u])
		{
			int v;
			double w;
			tie(v, w) = i;
			if (dist[v][0] > dist[u][0] + w)
				PQ.emplace(dist[v][0] = dist[u][0] + w, v);
		}
	}

	for (int i = 1; i <= K; i++)
	{
		for (int j = 0; j < N; j++)
			if (vis[j] && arr[j] == 0)
			{
				dist[j][i] = 0;
				PQ.emplace(0, j);
			}

		dist[0][i] = 0;
		PQ.emplace(0, 0);
		while (!PQ.empty())
		{
			int u;
			double d;
			tie(d, u) = PQ.top();
			PQ.pop();
			if (d != dist[u][i] || u == H)
				continue;

			for (pair<int, double> j : adj[u])
			{
				int v;
				double w;
				tie(v, w) = j;
				if (dist[v][i] > (dist[u][i - 1] + w) / 2.0 && arr[v] == 2)
					PQ.emplace(dist[v][i] = (dist[u][i - 1] + w) / 2.0, v);

				if (dist[v][i] > dist[u][i] + w)
					PQ.emplace(dist[v][i] = dist[u][i] + w, v);
			}
		}
	}

	return (dist[H][K] == INF ? -1 : dist[H][K]);
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	344 KB	Correct.
2	Correct	22 ms	516 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	85 ms	812 KB	Correct.
2	Correct	103 ms	848 KB	Correct.
3	Correct	99 ms	848 KB	Correct.
4	Correct	106 ms	836 KB	Correct.
5	Correct	104 ms	852 KB	Correct.
6	Correct	153 ms	4100 KB	Correct.
7	Correct	209 ms	4372 KB	Correct.
8	Correct	93 ms	8108 KB	Correct.
9	Correct	60 ms	544 KB	Correct.
10	Correct	58 ms	548 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	137 ms	852 KB	Correct.
2	Correct	132 ms	836 KB	Correct.
3	Correct	116 ms	860 KB	Correct.
4	Correct	75 ms	348 KB	Correct.
5	Correct	71 ms	592 KB	Correct.
6	Correct	41 ms	3676 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	106 ms	22608 KB	Correct.
2	Correct	84 ms	860 KB	Correct.
3	Correct	71 ms	816 KB	Correct.
4	Correct	75 ms	776 KB	Correct.
5	Correct	49 ms	344 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	62 ms	800 KB	Correct.
2	Correct	67 ms	756 KB	Correct.
3	Correct	71 ms	808 KB	Correct.
4	Correct	128 ms	3724 KB	Correct.
5	Correct	42 ms	348 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	80 ms	852 KB	Correct.
2	Correct	59 ms	832 KB	Correct.
3	Correct	51 ms	29268 KB	Correct.
4	Correct	74 ms	2640 KB	Correct.
5	Correct	50 ms	348 KB	Correct.
6	Correct	70 ms	808 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	99 ms	1184 KB	Correct.
2	Correct	17 ms	856 KB	Correct.
3	Correct	647 ms	27836 KB	Correct.
4	Correct	256 ms	7112 KB	Correct.
5	Correct	488 ms	17884 KB	Correct.
6	Correct	176 ms	9352 KB	Correct.
7	Correct	257 ms	7112 KB	Correct.
8	Correct	199 ms	2080 KB	Correct.
9	Correct	79 ms	880 KB	Correct.
10	Correct	76 ms	784 KB	Correct.
11	Correct	160 ms	856 KB	Correct.
12	Correct	95 ms	1520 KB	Correct.
13	Correct	85 ms	800 KB	Correct.
14	Correct	250 ms	9484 KB	Correct.
15	Correct	238 ms	2816 KB	Correct.
16	Correct	81 ms	812 KB	Correct.
17	Correct	99 ms	832 KB	Correct.
18	Correct	92 ms	796 KB	Correct.
19	Correct	306 ms	600 KB	Correct.
20	Correct	5 ms	348 KB	Correct.
21	Correct	7 ms	640 KB	Correct.
22	Correct	13 ms	1368 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	179 ms	1040 KB	Correct.
2	Correct	35 ms	1372 KB	Correct.
3	Correct	382 ms	69336 KB	Correct.
4	Correct	292 ms	3080 KB	Correct.
5	Correct	1035 ms	29048 KB	Correct.
6	Correct	417 ms	12964 KB	Correct.
7	Correct	517 ms	13444 KB	Correct.
8	Correct	219 ms	1392 KB	Correct.
9	Correct	142 ms	1120 KB	Correct.
10	Correct	138 ms	1132 KB	Correct.
11	Correct	120 ms	596 KB	Correct.
12	Correct	161 ms	1144 KB	Correct.
13	Correct	158 ms	1084 KB	Correct.
14	Correct	1377 ms	29136 KB	Correct.
15	Correct	1073 ms	34652 KB	Correct.
16	Correct	451 ms	12232 KB	Correct.
17	Correct	264 ms	3016 KB	Correct.
18	Correct	145 ms	1148 KB	Correct.
19	Correct	184 ms	1112 KB	Correct.
20	Correct	169 ms	1120 KB	Correct.
21	Correct	620 ms	1136 KB	Correct.
22	Correct	8 ms	348 KB	Correct.
23	Correct	11 ms	1008 KB	Correct.
24	Correct	27 ms	1628 KB	Correct.

Submission #975650

Compilation message