oj.uz

답안 #919224

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
919224 2024-01-31T13:11:25 Z MisterReaper 사이버랜드 (APIO23_cyberland) C++17
100 / 100
 1884 ms 84736 KB 
#include <bits/stdc++.h>
//#include "cyberland.h"
using i64 = long long;

struct DSU {
	int n;
	std::vector<int> par;
	DSU(int _n) : n(_n) {
		par.resize(n);
		std::iota(par.begin(), par.end(), 0);
	}

	int get(int x) {
		if(par[x] == x) {
			return x;
		}

		return par[x] = get(par[x]);
	}

	bool same(int a, int b) {
		return get(a) == get(b);
	}

	bool unite(int u, int v) {
		if(same(u, v)) {
			return false;
		}

		u = get(u);
		v = get(v);
		par[u] = v;

		return true;
	}
};

const double INF = 1E18;
const double EPS = 1E-6;

double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
	DSU dsu(N), dsu2(N);
	std::vector<std::pair<int, int>> adj[N];
	for(int i = 0; i < M; i++) {
		dsu.unite(x[i], y[i]);
		if(x[i] != H && y[i] != H) {
			dsu2.unite(x[i], y[i]);
		}

		adj[x[i]].emplace_back(y[i], c[i]);
		adj[y[i]].emplace_back(x[i], c[i]);
	}

	if(!dsu.same(0, H)) {
		return -1;
	}

	K = std::min(80, K);

	std::vector<double> pw(K + 1, 1);
	for(int i = 1; i <= K; i++) {
		pw[i] = pw[i - 1] / 2;
	}

	using T = std::tuple<double, int, int>;
	std::priority_queue<T, std::vector<T>, std::greater<T>> pq;
	pq.emplace(0, H, 0);

	std::vector dist(N, std::vector<double> (K + 1, -1));
	std::vector vis(N, std::vector<bool> (K + 1, false));
	double ans = INF;
	while(!pq.empty()) {
		auto [cost, node, bound] = pq.top();
		pq.pop();

		if(vis[node][bound]) {
			continue;
		}

		if(arr[node] == 0) {
			ans = std::min(ans, cost);
			break;
		}

		dist[node][bound] = cost;
		vis[node][bound] = true;

		for(auto [child, w] : adj[node]) {
			if(dsu2.same(0, child)) {
				pq.emplace(cost + w * pw[bound], child, bound);
				if(arr[node] == 2 && bound + 1 <= K) {
					pq.emplace(cost + w * pw[bound + 1], child, bound + 1);
				}
			}
		}
	}

	for(int i = 0; i <= K; i++) {
		if(vis[0][i]) {
			ans = std::min(ans, dist[0][i]);
		}
	}

	if(std::abs(ans - INF) <= EPS) {
		return -1;
	}

	return ans;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 1872 KB Correct.
2 Correct 41 ms 1876 KB Correct.
3 Correct 34 ms 1884 KB Correct.
4 Correct 34 ms 1872 KB Correct.
5 Correct 35 ms 1880 KB Correct.
6 Correct 36 ms 5596 KB Correct.
7 Correct 39 ms 5476 KB Correct.
8 Correct 25 ms 9820 KB Correct.
9 Correct 33 ms 1420 KB Correct.
10 Correct 33 ms 1360 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 1728 KB Correct.
2 Correct 24 ms 1760 KB Correct.
3 Correct 24 ms 1776 KB Correct.
4 Correct 25 ms 1424 KB Correct.
5 Correct 27 ms 1360 KB Correct.
6 Correct 6 ms 4184 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 27916 KB Correct.
2 Correct 27 ms 1872 KB Correct.
3 Correct 25 ms 1920 KB Correct.
4 Correct 27 ms 1904 KB Correct.
5 Correct 30 ms 1360 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 1648 KB Correct.
2 Correct 33 ms 2128 KB Correct.
3 Correct 34 ms 1908 KB Correct.
4 Correct 36 ms 5112 KB Correct.
5 Correct 25 ms 1160 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 1772 KB Correct.
2 Correct 20 ms 1692 KB Correct.
3 Correct 41 ms 9640 KB Correct.
4 Correct 14 ms 3664 KB Correct.
5 Correct 24 ms 1368 KB Correct.
6 Correct 23 ms 1704 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 1812 KB Correct.
2 Correct 4 ms 856 KB Correct.
3 Correct 69 ms 35604 KB Correct.
4 Correct 55 ms 10660 KB Correct.
5 Correct 51 ms 19808 KB Correct.
6 Correct 33 ms 8784 KB Correct.
7 Correct 51 ms 9760 KB Correct.
8 Correct 51 ms 3200 KB Correct.
9 Correct 21 ms 1724 KB Correct.
10 Correct 22 ms 1532 KB Correct.
11 Correct 54 ms 2280 KB Correct.
12 Correct 29 ms 1592 KB Correct.
13 Correct 25 ms 1548 KB Correct.
14 Correct 57 ms 13392 KB Correct.
15 Correct 50 ms 4932 KB Correct.
16 Correct 23 ms 1476 KB Correct.
17 Correct 26 ms 884 KB Correct.
18 Correct 27 ms 796 KB Correct.
19 Correct 51 ms 856 KB Correct.
20 Correct 3 ms 344 KB Correct.
21 Correct 2 ms 856 KB Correct.
22 Correct 3 ms 1112 KB Correct.

Subtask #8
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 1140 KB Correct.
2 Correct 4 ms 1112 KB Correct.
3 Correct 1884 ms 84736 KB Correct.
4 Correct 48 ms 5516 KB Correct.
5 Correct 53 ms 33676 KB Correct.
6 Correct 32 ms 13364 KB Correct.
7 Correct 52 ms 16996 KB Correct.
8 Correct 60 ms 3196 KB Correct.
9 Correct 25 ms 2260 KB Correct.
10 Correct 24 ms 1780 KB Correct.
11 Correct 520 ms 1796 KB Correct.
12 Correct 25 ms 2116 KB Correct.
13 Correct 28 ms 2272 KB Correct.
14 Correct 65 ms 34640 KB Correct.
15 Correct 63 ms 43548 KB Correct.
16 Correct 62 ms 14368 KB Correct.
17 Correct 54 ms 5220 KB Correct.
18 Correct 24 ms 2364 KB Correct.
19 Correct 25 ms 2316 KB Correct.
20 Correct 26 ms 2196 KB Correct.
21 Correct 47 ms 3048 KB Correct.
22 Correct 3 ms 600 KB Correct.
23 Correct 3 ms 856 KB Correct.
24 Correct 4 ms 1624 KB Correct.