oj.uz

답안 #975645

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
975645 2024-05-05T15:51:16 Z XXBabaProBerkay 사이버랜드 (APIO23_cyberland) C++17
97 / 100
 1185 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

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 848 KB Correct.
2 Correct 22 ms 856 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 1616 KB Correct.
2 Correct 104 ms 1880 KB Correct.
3 Correct 98 ms 1624 KB Correct.
4 Correct 113 ms 1720 KB Correct.
5 Correct 115 ms 1700 KB Correct.
6 Correct 151 ms 5000 KB Correct.
7 Correct 217 ms 5112 KB Correct.
8 Correct 91 ms 8280 KB Correct.
9 Correct 65 ms 1412 KB Correct.
10 Correct 60 ms 1256 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 132 ms 1700 KB Correct.
2 Correct 130 ms 1736 KB Correct.
3 Correct 117 ms 1640 KB Correct.
4 Correct 70 ms 1440 KB Correct.
5 Correct 72 ms 1360 KB Correct.
6 Correct 45 ms 3672 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 23952 KB Correct.
2 Correct 82 ms 1852 KB Correct.
3 Correct 68 ms 1628 KB Correct.
4 Correct 78 ms 1776 KB Correct.
5 Correct 50 ms 1304 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 1672 KB Correct.
2 Correct 67 ms 1800 KB Correct.
3 Correct 76 ms 2060 KB Correct.
4 Correct 132 ms 4484 KB Correct.
5 Correct 43 ms 1296 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 1844 KB Correct.
2 Correct 64 ms 1672 KB Correct.
3 Correct 51 ms 31216 KB Correct.
4 Correct 75 ms 3400 KB Correct.
5 Correct 53 ms 1296 KB Correct.
6 Correct 74 ms 1716 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 1924 KB Correct.
2 Correct 17 ms 1112 KB Correct.
3 Correct 749 ms 30288 KB Correct.
4 Correct 257 ms 9504 KB Correct.
5 Correct 567 ms 19632 KB Correct.
6 Correct 177 ms 10844 KB Correct.
7 Correct 264 ms 8376 KB Correct.
8 Correct 204 ms 3088 KB Correct.
9 Correct 84 ms 1752 KB Correct.
10 Correct 81 ms 1644 KB Correct.
11 Correct 160 ms 2628 KB Correct.
12 Correct 88 ms 1880 KB Correct.
13 Correct 85 ms 1788 KB Correct.
14 Correct 249 ms 10876 KB Correct.
15 Correct 248 ms 4804 KB Correct.
16 Correct 82 ms 1772 KB Correct.
17 Correct 98 ms 1884 KB Correct.
18 Correct 93 ms 1816 KB Correct.
19 Correct 318 ms 2640 KB Correct.
20 Correct 5 ms 604 KB Correct.
21 Correct 6 ms 808 KB Correct.
22 Correct 13 ms 1372 KB Correct.

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1185 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -