oj.uz

Submission #975646

# Submission time Handle Problem Language Result Execution time Memory
975646 2024-05-05T15:56:13 Z vjudge1 Cyberland (APIO23_cyberland) C++17
97 / 100
 954 ms 2097152 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)
{
	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 856 KB Correct.
2 Correct 23 ms 860 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 1684 KB Correct.
2 Correct 103 ms 1876 KB Correct.
3 Correct 99 ms 1620 KB Correct.
4 Correct 106 ms 1620 KB Correct.
5 Correct 102 ms 1872 KB Correct.
6 Correct 150 ms 5004 KB Correct.
7 Correct 221 ms 5216 KB Correct.
8 Correct 104 ms 8424 KB Correct.
9 Correct 62 ms 1364 KB Correct.
10 Correct 59 ms 1304 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 2224 KB Correct.
2 Correct 132 ms 1740 KB Correct.
3 Correct 116 ms 1784 KB Correct.
4 Correct 71 ms 1292 KB Correct.
5 Correct 76 ms 1412 KB Correct.
6 Correct 41 ms 3676 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 23892 KB Correct.
2 Correct 84 ms 1872 KB Correct.
3 Correct 69 ms 1832 KB Correct.
4 Correct 78 ms 1748 KB Correct.
5 Correct 50 ms 1368 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 1708 KB Correct.
2 Correct 67 ms 1872 KB Correct.
3 Correct 76 ms 2140 KB Correct.
4 Correct 130 ms 4488 KB Correct.
5 Correct 42 ms 1168 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 1708 KB Correct.
2 Correct 59 ms 1728 KB Correct.
3 Correct 54 ms 31336 KB Correct.
4 Correct 76 ms 3464 KB Correct.
5 Correct 51 ms 1364 KB Correct.
6 Correct 72 ms 1816 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 1756 KB Correct.
2 Correct 17 ms 1116 KB Correct.
3 Correct 704 ms 30252 KB Correct.
4 Correct 254 ms 9412 KB Correct.
5 Correct 512 ms 19668 KB Correct.
6 Correct 190 ms 10888 KB Correct.
7 Correct 259 ms 8396 KB Correct.
8 Correct 198 ms 3036 KB Correct.
9 Correct 78 ms 1740 KB Correct.
10 Correct 77 ms 1732 KB Correct.
11 Correct 166 ms 2604 KB Correct.
12 Correct 97 ms 1832 KB Correct.
13 Correct 85 ms 1888 KB Correct.
14 Correct 249 ms 11032 KB Correct.
15 Correct 246 ms 4952 KB Correct.
16 Correct 82 ms 1796 KB Correct.
17 Correct 100 ms 1876 KB Correct.
18 Correct 92 ms 1816 KB Correct.
19 Correct 312 ms 2592 KB Correct.
20 Correct 5 ms 604 KB Correct.
21 Correct 6 ms 772 KB Correct.
22 Correct 13 ms 1372 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 954 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -