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
#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]);
}
# Verdict Execution time Memory Grader output
1 Correct 22 ms 860 KB Correct.
2 Correct 22 ms 860 KB Correct.
# 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.
# 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.
# 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.
# 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.
# 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.
# 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.
# 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.