oj.uz

답안 #749159

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
749159 2023-05-27T12:16:13 Z gun_gan 사이버랜드 (APIO23_cyberland) C++17
100 / 100
 2601 ms 16732 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 <= min(85, 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 42 ms 340 KB Correct.
2 Correct 45 ms 384 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 300 ms 456 KB Correct.
2 Correct 352 ms 496 KB Correct.
3 Correct 327 ms 708 KB Correct.
4 Correct 345 ms 460 KB Correct.
5 Correct 352 ms 524 KB Correct.
6 Correct 410 ms 2016 KB Correct.
7 Correct 544 ms 2012 KB Correct.
8 Correct 234 ms 3748 KB Correct.
9 Correct 184 ms 404 KB Correct.
10 Correct 185 ms 412 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 410 ms 508 KB Correct.
2 Correct 375 ms 636 KB Correct.
3 Correct 344 ms 620 KB Correct.
4 Correct 220 ms 540 KB Correct.
5 Correct 217 ms 416 KB Correct.
6 Correct 99 ms 1896 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 198 ms 8476 KB Correct.
2 Correct 215 ms 468 KB Correct.
3 Correct 187 ms 544 KB Correct.
4 Correct 196 ms 492 KB Correct.
5 Correct 123 ms 388 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 160 ms 448 KB Correct.
2 Correct 169 ms 436 KB Correct.
3 Correct 184 ms 500 KB Correct.
4 Correct 244 ms 1712 KB Correct.
5 Correct 91 ms 396 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 219 ms 460 KB Correct.
2 Correct 176 ms 488 KB Correct.
3 Correct 49 ms 10204 KB Correct.
4 Correct 152 ms 1632 KB Correct.
5 Correct 126 ms 340 KB Correct.
6 Correct 184 ms 504 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 236 ms 460 KB Correct.
2 Correct 29 ms 556 KB Correct.
3 Correct 1025 ms 16412 KB Correct.
4 Correct 631 ms 4056 KB Correct.
5 Correct 695 ms 9604 KB Correct.
6 Correct 306 ms 6100 KB Correct.
7 Correct 612 ms 4364 KB Correct.
8 Correct 472 ms 956 KB Correct.
9 Correct 188 ms 492 KB Correct.
10 Correct 183 ms 464 KB Correct.
11 Correct 440 ms 720 KB Correct.
12 Correct 205 ms 456 KB Correct.
13 Correct 198 ms 580 KB Correct.
14 Correct 487 ms 8460 KB Correct.
15 Correct 506 ms 2408 KB Correct.
16 Correct 200 ms 536 KB Correct.
17 Correct 226 ms 524 KB Correct.
18 Correct 220 ms 500 KB Correct.
19 Correct 627 ms 468 KB Correct.
20 Correct 11 ms 340 KB Correct.
21 Correct 15 ms 340 KB Correct.
22 Correct 21 ms 920 KB Correct.

Subtask #8
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 578 ms 472 KB Correct.
2 Correct 91 ms 468 KB Correct.
3 Correct 2243 ms 16732 KB Correct.
4 Correct 759 ms 1384 KB Correct.
5 Correct 1886 ms 9648 KB Correct.
6 Correct 745 ms 6308 KB Correct.
7 Correct 1110 ms 6816 KB Correct.
8 Correct 678 ms 924 KB Correct.
9 Correct 435 ms 444 KB Correct.
10 Correct 467 ms 588 KB Correct.
11 Correct 339 ms 552 KB Correct.
12 Correct 490 ms 480 KB Correct.
13 Correct 478 ms 536 KB Correct.
14 Correct 2370 ms 8556 KB Correct.
15 Correct 2601 ms 8756 KB Correct.
16 Correct 1036 ms 3444 KB Correct.
17 Correct 741 ms 1008 KB Correct.
18 Correct 449 ms 436 KB Correct.
19 Correct 555 ms 448 KB Correct.
20 Correct 525 ms 676 KB Correct.
21 Correct 1616 ms 468 KB Correct.
22 Correct 24 ms 340 KB Correct.
23 Correct 36 ms 420 KB Correct.
24 Correct 50 ms 852 KB Correct.