oj.uz

답안 #750800

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
750800 2023-05-30T10:13:32 Z rxlfd314 사이버랜드 (APIO23_cyberland) C++17
100 / 100
 1236 ms 74968 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
	vector<pair<int, double>> adj[N];
	for (int i = 0; i < M; i++) {
		adj[x[i]].push_back({y[i], (double)c[i]});
		adj[y[i]].push_back({x[i], (double)c[i]});
	}
	
	bool useful[N] = {};
	queue<int> qu;
	qu.push(0);
	useful[0] = true;
	while (qu.size()) {
		int f = qu.front();
		qu.pop();
		if (f == H) continue;
		for (auto [nf, _] : adj[f]) {
			if (!useful[nf]) {
				useful[nf] = true;
				qu.push(nf);
			}
		}
	}
	
	if (!useful[H]) return -1;
	
	vector<vector<double>> dst(min(K, 80)+1, vector<double>(N, 1e14));
	double ans = 1e14;
	for (int ii = 0; ii <= min(K, 80); ii++) {
		priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;
		for (int i = 0; i < N; i++) {
			if (!useful[i]) continue;
			if (arr[i] == 2 && ii) {
				for (auto [j, v] : adj[i]) {
					if (!useful[j] || j == H) continue;
					dst[ii][i] = min(dst[ii][i], (dst[ii-1][j] + v) / 2.0);
				}
				pq.push({dst[ii][i], i});
			} else if (!arr[i]) {
				dst[ii][i] = 0;
				pq.push({0, i});
			}
		}
		if (!ii) {
			dst[0][0] = 0;
			pq.push({0, 0});
		}
		
		while (pq.size()) {
			auto [d, f] = pq.top();
			pq.pop();
			if (d > dst[ii][f] || f == H) continue;
			for (auto [nf, v] : adj[f]) {
				if (d + v < dst[ii][nf] && useful[nf]) {
					dst[ii][nf] = d + v;
					pq.push({d+v, nf});
				}
			}
		}
		
		ans = min(ans, dst[ii][H]);
	}
	
	return ans;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 452 KB Correct.
2 Correct 29 ms 468 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 724 KB Correct.
2 Correct 33 ms 700 KB Correct.
3 Correct 32 ms 752 KB Correct.
4 Correct 38 ms 680 KB Correct.
5 Correct 35 ms 692 KB Correct.
6 Correct 29 ms 3700 KB Correct.
7 Correct 37 ms 3684 KB Correct.
8 Correct 16 ms 7380 KB Correct.
9 Correct 29 ms 468 KB Correct.
10 Correct 29 ms 496 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 145 ms 848 KB Correct.
2 Correct 137 ms 668 KB Correct.
3 Correct 132 ms 708 KB Correct.
4 Correct 92 ms 468 KB Correct.
5 Correct 91 ms 484 KB Correct.
6 Correct 43 ms 3364 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 20856 KB Correct.
2 Correct 96 ms 700 KB Correct.
3 Correct 94 ms 784 KB Correct.
4 Correct 87 ms 688 KB Correct.
5 Correct 62 ms 492 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 680 KB Correct.
2 Correct 28 ms 664 KB Correct.
3 Correct 29 ms 664 KB Correct.
4 Correct 28 ms 3484 KB Correct.
5 Correct 24 ms 432 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 724 KB Correct.
2 Correct 61 ms 704 KB Correct.
3 Correct 42 ms 8568 KB Correct.
4 Correct 69 ms 2608 KB Correct.
5 Correct 53 ms 484 KB Correct.
6 Correct 72 ms 688 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 648 KB Correct.
2 Correct 17 ms 852 KB Correct.
3 Correct 438 ms 24628 KB Correct.
4 Correct 292 ms 6456 KB Correct.
5 Correct 324 ms 17132 KB Correct.
6 Correct 140 ms 9240 KB Correct.
7 Correct 261 ms 6556 KB Correct.
8 Correct 206 ms 1436 KB Correct.
9 Correct 73 ms 684 KB Correct.
10 Correct 69 ms 668 KB Correct.
11 Correct 192 ms 768 KB Correct.
12 Correct 82 ms 648 KB Correct.
13 Correct 87 ms 688 KB Correct.
14 Correct 245 ms 8224 KB Correct.
15 Correct 256 ms 2520 KB Correct.
16 Correct 85 ms 620 KB Correct.
17 Correct 95 ms 772 KB Correct.
18 Correct 80 ms 680 KB Correct.
19 Correct 225 ms 724 KB Correct.
20 Correct 5 ms 340 KB Correct.
21 Correct 6 ms 468 KB Correct.
22 Correct 10 ms 1212 KB Correct.

Subtask #8
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 172 ms 1008 KB Correct.
2 Correct 29 ms 1108 KB Correct.
3 Correct 273 ms 74968 KB Correct.
4 Correct 284 ms 3412 KB Correct.
5 Correct 817 ms 31312 KB Correct.
6 Correct 302 ms 13316 KB Correct.
7 Correct 539 ms 14352 KB Correct.
8 Correct 261 ms 1416 KB Correct.
9 Correct 151 ms 1116 KB Correct.
10 Correct 126 ms 972 KB Correct.
11 Correct 199 ms 548 KB Correct.
12 Correct 161 ms 1024 KB Correct.
13 Correct 155 ms 1024 KB Correct.
14 Correct 1236 ms 31200 KB Correct.
15 Correct 981 ms 37492 KB Correct.
16 Correct 426 ms 11584 KB Correct.
17 Correct 296 ms 3000 KB Correct.
18 Correct 145 ms 1208 KB Correct.
19 Correct 208 ms 1108 KB Correct.
20 Correct 156 ms 1016 KB Correct.
21 Correct 491 ms 1176 KB Correct.
22 Correct 8 ms 340 KB Correct.
23 Correct 12 ms 664 KB Correct.
24 Correct 20 ms 1608 KB Correct.