Submission #975649

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
975649	2024-05-05T16:00:17 Z	XXBabaProBerkay	Cyberland (APIO23_cyberland)	C++17	100 / 100	1347 ms	71768 KB

cyberland

#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	860 KB	Correct.
2	Correct	22 ms	860 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	85 ms	1700 KB	Correct.
2	Correct	109 ms	1876 KB	Correct.
3	Correct	99 ms	1616 KB	Correct.
4	Correct	107 ms	1840 KB	Correct.
5	Correct	104 ms	1832 KB	Correct.
6	Correct	159 ms	4864 KB	Correct.
7	Correct	201 ms	5212 KB	Correct.
8	Correct	95 ms	8344 KB	Correct.
9	Correct	60 ms	1360 KB	Correct.
10	Correct	60 ms	1380 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	135 ms	1800 KB	Correct.
2	Correct	131 ms	1728 KB	Correct.
3	Correct	117 ms	1736 KB	Correct.
4	Correct	70 ms	1364 KB	Correct.
5	Correct	70 ms	1360 KB	Correct.
6	Correct	42 ms	3676 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	106 ms	23888 KB	Correct.
2	Correct	88 ms	1700 KB	Correct.
3	Correct	69 ms	1832 KB	Correct.
4	Correct	76 ms	1768 KB	Correct.
5	Correct	49 ms	1312 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	71 ms	2032 KB	Correct.
2	Correct	68 ms	1808 KB	Correct.
3	Correct	72 ms	1816 KB	Correct.
4	Correct	130 ms	4484 KB	Correct.
5	Correct	42 ms	1112 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	79 ms	1616 KB	Correct.
2	Correct	60 ms	1696 KB	Correct.
3	Correct	52 ms	31092 KB	Correct.
4	Correct	79 ms	3412 KB	Correct.
5	Correct	53 ms	1360 KB	Correct.
6	Correct	70 ms	1832 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	98 ms	1788 KB	Correct.
2	Correct	18 ms	1116 KB	Correct.
3	Correct	668 ms	30256 KB	Correct.
4	Correct	261 ms	9368 KB	Correct.
5	Correct	506 ms	19668 KB	Correct.
6	Correct	179 ms	10864 KB	Correct.
7	Correct	261 ms	8248 KB	Correct.
8	Correct	198 ms	3012 KB	Correct.
9	Correct	78 ms	1776 KB	Correct.
10	Correct	78 ms	1688 KB	Correct.
11	Correct	162 ms	2576 KB	Correct.
12	Correct	89 ms	1796 KB	Correct.
13	Correct	86 ms	1792 KB	Correct.
14	Correct	255 ms	11108 KB	Correct.
15	Correct	243 ms	4792 KB	Correct.
16	Correct	82 ms	1768 KB	Correct.
17	Correct	102 ms	1856 KB	Correct.
18	Correct	92 ms	1800 KB	Correct.
19	Correct	305 ms	2724 KB	Correct.
20	Correct	5 ms	604 KB	Correct.
21	Correct	6 ms	736 KB	Correct.
22	Correct	13 ms	1372 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	176 ms	2048 KB	Correct.
2	Correct	33 ms	1628 KB	Correct.
3	Correct	421 ms	71768 KB	Correct.
4	Correct	290 ms	4812 KB	Correct.
5	Correct	1049 ms	30924 KB	Correct.
6	Correct	408 ms	14552 KB	Correct.
7	Correct	516 ms	14572 KB	Correct.
8	Correct	222 ms	3296 KB	Correct.
9	Correct	140 ms	2020 KB	Correct.
10	Correct	144 ms	1984 KB	Correct.
11	Correct	122 ms	1532 KB	Correct.
12	Correct	161 ms	2168 KB	Correct.
13	Correct	156 ms	2140 KB	Correct.
14	Correct	1347 ms	30564 KB	Correct.
15	Correct	1129 ms	36684 KB	Correct.
16	Correct	452 ms	13512 KB	Correct.
17	Correct	270 ms	4860 KB	Correct.
18	Correct	147 ms	2116 KB	Correct.
19	Correct	184 ms	2148 KB	Correct.
20	Correct	170 ms	2084 KB	Correct.
21	Correct	621 ms	2924 KB	Correct.
22	Correct	8 ms	604 KB	Correct.
23	Correct	11 ms	1116 KB	Correct.
24	Correct	26 ms	1624 KB	Correct.

Submission #975649

Compilation message