oj.uz

답안 #749151

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
749151 2023-05-27T12:11:22 Z gun_gan 사이버랜드 (APIO23_cyberland) C++17
97 / 100
 3000 ms 16512 KB 
#include <bits/stdc++.h>
#include "cyberland.h"
using namespace std;
typedef long long ll;

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,int>>> g(N);
	for(int i = 0; i < M; i++) {
		g[x[i]].push_back({y[i], c[i]});
		g[y[i]].push_back({x[i], c[i]});
	}
	priority_queue<pair<double,int>> pq;

	vector<double> dd(N, 1e18);
	
	{
		dd[0] = 0;
		pq.push({0, 0});

		while(!pq.empty()) {
			auto [x, v] = pq.top(); pq.pop();
			x = -x;
			if(dd[v] < x) continue;
			for(auto [u, w] : g[v]) {
				if(dd[u] > x + w && u != H) {
					dd[u] = x + w;
					pq.push({-dd[u], u});
				}
			} 
		}
	}

	vector<array<double, 2>> d(N, {1e18, 1e18});

	arr[0] = 0;
	for(int i = 0; i < N; i++) if(!arr[i] && dd[i] == 1e18) arr[i] = 1;

	{
		for(int i = 0; i < N; i++) {
			if(!arr[i] && dd[i] != 1e18) {
				d[i][1] = 0;
				pq.push({0, i});
			}
		}

		while(!pq.empty()) {
			auto [x, v] = pq.top(); pq.pop();
			x = -x;
			if(d[v][1] < x) continue;
			for(auto [u, w] : g[v]) {
				if(d[u][1] > x + w && u != H) {
					d[u][1] = x + w;
					pq.push({-d[u][1], u});
				}
			} 
		}
	}


	double res = 1e18;

	for(auto [u, w] : g[H]) {
		res = min(res, d[u][1] + w);
	}

	for(int k = 1; k <= K; k++) {
		vector<array<double,2>> nd(N, {1e18, 1e18});

		priority_queue<pair<double,pair<int, int>>> pq;
		for(int i = 0; i < N; i++) {
			nd[i][0] = min(d[i][0], d[i][1]);
			if(arr[i] == 2 && nd[i][0] != 1e18) {
				nd[i][0] = min(nd[i][0], d[i][1] / 2);
			}
			if(nd[i][0] != 1e18) pq.push({-nd[i][0], {i, 0}});
		}

		while(!pq.empty()) {
			auto [x, p] = pq.top(); 
			auto [v, c] = p;
			pq.pop();

			x = -x;
			if(nd[v][c] < x) continue;
			for(auto [u, w] : g[v]) {
				if(nd[u][c | 1] > x + w && u != H) {
					nd[u][c | 1] = x + w;
					pq.push({-nd[u][c | 1], {u, c | 1}});
				}
			} 
		}

		swap(nd, d);
		for(auto [u, w] : g[H]) {
			res = min(res, min(d[u][0], d[u][1]) + w);
		}
	}

	if(res == 1e18) res = -1;
	return res;
}	

// int main() {
// 	cin.tie(0); ios_base::sync_with_stdio(0);

// 	// cout << fixed << setprecision(1) << solve(4, 4, 30, 3, {0, 0, 1, 2}, {1, 2, 3, 3}, {5, 4, 2, 4}, {1, 0, 2, 1}) << '\n';
// 	// cout << fixed << setprecision(1) << solve(3, 2, 30, 2, {1, 2}, {2, 0}, {12, 4}, {1, 2, 1}) << '\n';
// 	cout << fixed << setprecision(1) << solve(4, 3, 3, 3, {0, 1, 2}, {1, 2, 3}, {11, 1, 10}, {1, 1, 2, 1}) << '\n';
// }

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 416 KB Correct.
2 Correct 43 ms 436 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 296 ms 596 KB Correct.
2 Correct 354 ms 616 KB Correct.
3 Correct 331 ms 496 KB Correct.
4 Correct 354 ms 460 KB Correct.
5 Correct 342 ms 536 KB Correct.
6 Correct 410 ms 2012 KB Correct.
7 Correct 552 ms 2084 KB Correct.
8 Correct 240 ms 3728 KB Correct.
9 Correct 179 ms 416 KB Correct.
10 Correct 174 ms 396 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 382 ms 504 KB Correct.
2 Correct 379 ms 752 KB Correct.
3 Correct 346 ms 736 KB Correct.
4 Correct 207 ms 492 KB Correct.
5 Correct 206 ms 532 KB Correct.
6 Correct 94 ms 1892 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 207 ms 8624 KB Correct.
2 Correct 214 ms 460 KB Correct.
3 Correct 189 ms 628 KB Correct.
4 Correct 202 ms 520 KB Correct.
5 Correct 127 ms 392 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 508 KB Correct.
2 Correct 161 ms 448 KB Correct.
3 Correct 180 ms 460 KB Correct.
4 Correct 231 ms 1708 KB Correct.
5 Correct 102 ms 520 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 220 ms 452 KB Correct.
2 Correct 162 ms 496 KB Correct.
3 Correct 48 ms 10188 KB Correct.
4 Correct 152 ms 1692 KB Correct.
5 Correct 136 ms 408 KB Correct.
6 Correct 187 ms 492 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 219 ms 444 KB Correct.
2 Correct 29 ms 552 KB Correct.
3 Correct 951 ms 16512 KB Correct.
4 Correct 618 ms 3968 KB Correct.
5 Correct 705 ms 9540 KB Correct.
6 Correct 281 ms 6116 KB Correct.
7 Correct 591 ms 4292 KB Correct.
8 Correct 478 ms 1092 KB Correct.
9 Correct 185 ms 520 KB Correct.
10 Correct 182 ms 596 KB Correct.
11 Correct 425 ms 816 KB Correct.
12 Correct 202 ms 444 KB Correct.
13 Correct 198 ms 576 KB Correct.
14 Correct 502 ms 8228 KB Correct.
15 Correct 494 ms 2512 KB Correct.
16 Correct 198 ms 452 KB Correct.
17 Correct 230 ms 440 KB Correct.
18 Correct 213 ms 468 KB Correct.
19 Correct 634 ms 508 KB Correct.
20 Correct 11 ms 388 KB Correct.
21 Correct 16 ms 340 KB Correct.
22 Correct 24 ms 932 KB Correct.

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3068 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -