oj.uz

답안 #768176

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
768176 2023-06-27T16:27:25 Z green_gold_dog 사이버랜드 (APIO23_cyberland) C++17
100 / 100
 1889 ms 23796 KB 
#include "cyberland.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF = 1'000'000'000'000'000'000;

void dfs(ll v, ll h, vector<vector<pair<ll, ll>>>& g, vector<bool>& used) {
	used[v] = true;
	if (v == h) {
		return;
	}
	for (auto[i, _] : g[v]) {
		if (!used[i]) {
			dfs(i, h, g, used);
		}
	}
}

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<ll, ll>>> g(n);
	for (ll i = 0; i < m; i++) {
		g[x[i]].emplace_back(y[i], c[i]);
		g[y[i]].emplace_back(x[i], c[i]);
	}
	vector<bool> used(n, false);
	dfs(0, h, g, used);
	if (!used[h]) {
		return -1;
	}
	vector<double> dist(n, INF);
	dist[0] = 0;
	for (ll i = 0; i < n; i++) {
		if (arr[i] == 0 && used[i]) {
			dist[i] = 0;
		}
	}
	if (k > 70) {
		k = 70;
	}
	for (ll nd = 0; nd <= k; nd++) {
		set<pair<double, ll>> pq;
		for (ll i = 0; i < n; i++) {
			if (dist[i] != INF) {
				pq.insert(make_pair(dist[i], i));
			}
		}
		while (!pq.empty()) {
			auto[d, v] = *pq.begin();
			pq.erase(pq.begin());
			if (v == h) {
				continue;
			}
			for (auto[i, c] : g[v]) {
				if (c + d < dist[i]) {
					pq.erase(make_pair(dist[i], i));
					dist[i] = c + d;
					pq.insert(make_pair(dist[i], i));
				}
			}
		}
		if (nd == k) {
			continue;
		}
		vector<pair<ll, double>> upd;
		for (ll i = 0; i < n; i++) {
			if (arr[i] == 2 && dist[i] != INF) {
				dist[i] /= 2;
				for (auto[v, c] : g[i]) {
					upd.emplace_back(v, c + dist[i]);
				}
				dist[i] = INF;
			}
		}
		for (auto[v, d] : upd) {
			if (dist[v] > d) {
				dist[v] = d;
			}
		}
	}
	return dist[h];
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 460 KB Correct.
2 Correct 34 ms 388 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 159 ms 524 KB Correct.
2 Correct 193 ms 492 KB Correct.
3 Correct 184 ms 488 KB Correct.
4 Correct 198 ms 592 KB Correct.
5 Correct 189 ms 524 KB Correct.
6 Correct 237 ms 1972 KB Correct.
7 Correct 311 ms 1936 KB Correct.
8 Correct 148 ms 3668 KB Correct.
9 Correct 113 ms 376 KB Correct.
10 Correct 111 ms 376 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 191 ms 480 KB Correct.
2 Correct 181 ms 468 KB Correct.
3 Correct 164 ms 492 KB Correct.
4 Correct 124 ms 360 KB Correct.
5 Correct 127 ms 376 KB Correct.
6 Correct 43 ms 1620 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 142 ms 8472 KB Correct.
2 Correct 153 ms 508 KB Correct.
3 Correct 138 ms 528 KB Correct.
4 Correct 150 ms 544 KB Correct.
5 Correct 87 ms 380 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 480 KB Correct.
2 Correct 73 ms 504 KB Correct.
3 Correct 81 ms 528 KB Correct.
4 Correct 118 ms 1660 KB Correct.
5 Correct 49 ms 384 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 524 KB Correct.
2 Correct 59 ms 492 KB Correct.
3 Correct 33 ms 8532 KB Correct.
4 Correct 70 ms 1688 KB Correct.
5 Correct 58 ms 340 KB Correct.
6 Correct 71 ms 508 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 132 ms 432 KB Correct.
2 Correct 20 ms 596 KB Correct.
3 Correct 953 ms 17676 KB Correct.
4 Correct 580 ms 4060 KB Correct.
5 Correct 492 ms 11964 KB Correct.
6 Correct 171 ms 8812 KB Correct.
7 Correct 535 ms 4560 KB Correct.
8 Correct 388 ms 1008 KB Correct.
9 Correct 108 ms 584 KB Correct.
10 Correct 98 ms 504 KB Correct.
11 Correct 320 ms 664 KB Correct.
12 Correct 127 ms 464 KB Correct.
13 Correct 122 ms 544 KB Correct.
14 Correct 465 ms 9064 KB Correct.
15 Correct 437 ms 2552 KB Correct.
16 Correct 111 ms 460 KB Correct.
17 Correct 146 ms 516 KB Correct.
18 Correct 127 ms 484 KB Correct.
19 Correct 370 ms 492 KB Correct.
20 Correct 7 ms 340 KB Correct.
21 Correct 9 ms 340 KB Correct.
22 Correct 13 ms 1268 KB Correct.

Subtask #8
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 260 ms 520 KB Correct.
2 Correct 40 ms 596 KB Correct.
3 Correct 1061 ms 23796 KB Correct.
4 Correct 569 ms 1472 KB Correct.
5 Correct 1058 ms 11924 KB Correct.
6 Correct 366 ms 9012 KB Correct.
7 Correct 773 ms 7300 KB Correct.
8 Correct 446 ms 732 KB Correct.
9 Correct 214 ms 444 KB Correct.
10 Correct 189 ms 616 KB Correct.
11 Correct 234 ms 464 KB Correct.
12 Correct 250 ms 468 KB Correct.
13 Correct 243 ms 604 KB Correct.
14 Correct 1602 ms 10252 KB Correct.
15 Correct 1889 ms 9012 KB Correct.
16 Correct 881 ms 3612 KB Correct.
17 Correct 547 ms 1012 KB Correct.
18 Correct 213 ms 480 KB Correct.
19 Correct 292 ms 540 KB Correct.
20 Correct 240 ms 456 KB Correct.
21 Correct 776 ms 496 KB Correct.
22 Correct 11 ms 340 KB Correct.
23 Correct 16 ms 420 KB Correct.
24 Correct 25 ms 1272 KB Correct.