oj.uz

답안 #750851

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
750851 2023-05-30T11:48:28 Z josanneo22 사이버랜드 (APIO23_cyberland) C++17
100 / 100
 262 ms 64988 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<int, 2>;
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
const int MAXN = 100005;

struct disj {
	int pa[MAXN];
	void init(int n) { iota(pa, pa + n + 1, 0); }
	int find(int x) { return pa[x] = (pa[x] == x ? x : find(pa[x])); }
	bool uni(int p, int q) {
		p = find(p);
		q = find(q);
		if (p == q)
			return 0;
		pa[q] = p;
		return 1;
	}
} disj;

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) {
	K = min(K, 69);
	vector<vector<pi>> gph(N);
	disj.init(N);
	for (int i = 0; i < M; i++) {
		if (x[i] != H && y[i] != H)
			disj.uni(x[i], y[i]);
		gph[x[i]].push_back({c[i], y[i]});
		gph[y[i]].push_back({c[i], x[i]});
	}
	vector<double> pwr(K + 1, 1);
	for (int i = 1; i <= K; i++)
		pwr[i] = pwr[i - 1] / 2;
	arr[0] = 0;
	vector<vector<double>> dist(K + 1, vector<double>(N, 1e18));
	using node = tuple<double, int, int>;
	priority_queue<node, vector<node>, greater<node>> pq;
	auto enq = [&](int k, int x, double d) {
		if (dist[k][x] > d) {
			dist[k][x] = d;
			pq.push({d, k, x});
		}
	};
	enq(K, H, 0);
	while (sz(pq)) {
		auto [d, k, v] = pq.top();
		pq.pop();
		if (dist[k][v] < d)
			continue;
		if (arr[v] == 0)
			return d;
		for (auto &[c, w] : gph[v]) {
			if (disj.find(w) != disj.find(0))
				continue;

			enq(k, w, d + c * pwr[K - k]);
			if (arr[v] == 2 && k > 0) {
				enq(k - 1, w, d + c * pwr[K - k + 1]);
			}
		}
	}
	return -1;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 728 KB Correct.
2 Correct 26 ms 700 KB Correct.
3 Correct 26 ms 728 KB Correct.
4 Correct 29 ms 688 KB Correct.
5 Correct 29 ms 728 KB Correct.
6 Correct 28 ms 3636 KB Correct.
7 Correct 29 ms 3668 KB Correct.
8 Correct 12 ms 7140 KB Correct.
9 Correct 26 ms 504 KB Correct.
10 Correct 26 ms 468 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 660 KB Correct.
2 Correct 25 ms 696 KB Correct.
3 Correct 25 ms 752 KB Correct.
4 Correct 30 ms 496 KB Correct.
5 Correct 26 ms 468 KB Correct.
6 Correct 5 ms 3028 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 20172 KB Correct.
2 Correct 26 ms 688 KB Correct.
3 Correct 23 ms 784 KB Correct.
4 Correct 23 ms 668 KB Correct.
5 Correct 27 ms 496 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 672 KB Correct.
2 Correct 27 ms 656 KB Correct.
3 Correct 26 ms 708 KB Correct.
4 Correct 26 ms 3552 KB Correct.
5 Correct 24 ms 468 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 680 KB Correct.
2 Correct 22 ms 732 KB Correct.
3 Correct 55 ms 26496 KB Correct.
4 Correct 17 ms 2336 KB Correct.
5 Correct 32 ms 492 KB Correct.
6 Correct 29 ms 696 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 708 KB Correct.
2 Correct 4 ms 852 KB Correct.
3 Correct 56 ms 23532 KB Correct.
4 Correct 50 ms 6192 KB Correct.
5 Correct 47 ms 14816 KB Correct.
6 Correct 29 ms 7000 KB Correct.
7 Correct 48 ms 6232 KB Correct.
8 Correct 49 ms 1468 KB Correct.
9 Correct 24 ms 712 KB Correct.
10 Correct 29 ms 684 KB Correct.
11 Correct 53 ms 720 KB Correct.
12 Correct 26 ms 736 KB Correct.
13 Correct 25 ms 812 KB Correct.
14 Correct 61 ms 7636 KB Correct.
15 Correct 45 ms 2316 KB Correct.
16 Correct 24 ms 700 KB Correct.
17 Correct 26 ms 756 KB Correct.
18 Correct 25 ms 720 KB Correct.
19 Correct 50 ms 652 KB Correct.
20 Correct 3 ms 468 KB Correct.
21 Correct 2 ms 624 KB Correct.
22 Correct 4 ms 980 KB Correct.

Subtask #8
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 1028 KB Correct.
2 Correct 4 ms 1364 KB Correct.
3 Correct 86 ms 64988 KB Correct.
4 Correct 63 ms 2752 KB Correct.
5 Correct 48 ms 25676 KB Correct.
6 Correct 33 ms 10204 KB Correct.
7 Correct 54 ms 12500 KB Correct.
8 Correct 53 ms 1348 KB Correct.
9 Correct 28 ms 1004 KB Correct.
10 Correct 27 ms 988 KB Correct.
11 Correct 262 ms 496 KB Correct.
12 Correct 30 ms 992 KB Correct.
13 Correct 28 ms 1004 KB Correct.
14 Correct 67 ms 26392 KB Correct.
15 Correct 81 ms 32560 KB Correct.
16 Correct 56 ms 11100 KB Correct.
17 Correct 59 ms 2716 KB Correct.
18 Correct 30 ms 972 KB Correct.
19 Correct 31 ms 1008 KB Correct.
20 Correct 29 ms 1012 KB Correct.
21 Correct 58 ms 964 KB Correct.
22 Correct 3 ms 468 KB Correct.
23 Correct 3 ms 884 KB Correct.
24 Correct 4 ms 1236 KB Correct.