oj.uz

답안 #985361

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
985361 2024-05-17T16:44:18 Z CrazyBotBoy 사이버랜드 (APIO23_cyberland) C++17
100 / 100
 183 ms 67548 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 21 ms 604 KB Correct.
2 Correct 22 ms 860 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 876 KB Correct.
2 Correct 23 ms 772 KB Correct.
3 Correct 21 ms 820 KB Correct.
4 Correct 22 ms 844 KB Correct.
5 Correct 21 ms 916 KB Correct.
6 Correct 18 ms 3660 KB Correct.
7 Correct 24 ms 3624 KB Correct.
8 Correct 11 ms 7260 KB Correct.
9 Correct 22 ms 648 KB Correct.
10 Correct 22 ms 604 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 792 KB Correct.
2 Correct 25 ms 1776 KB Correct.
3 Correct 20 ms 1080 KB Correct.
4 Correct 22 ms 1372 KB Correct.
5 Correct 24 ms 1540 KB Correct.
6 Correct 5 ms 3164 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 20304 KB Correct.
2 Correct 20 ms 1876 KB Correct.
3 Correct 18 ms 1832 KB Correct.
4 Correct 20 ms 1764 KB Correct.
5 Correct 28 ms 1392 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 808 KB Correct.
2 Correct 27 ms 792 KB Correct.
3 Correct 22 ms 840 KB Correct.
4 Correct 21 ms 3688 KB Correct.
5 Correct 20 ms 604 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 820 KB Correct.
2 Correct 19 ms 1728 KB Correct.
3 Correct 44 ms 28404 KB Correct.
4 Correct 14 ms 3064 KB Correct.
5 Correct 22 ms 1408 KB Correct.
6 Correct 20 ms 1744 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 812 KB Correct.
2 Correct 3 ms 1116 KB Correct.
3 Correct 48 ms 25840 KB Correct.
4 Correct 44 ms 8592 KB Correct.
5 Correct 42 ms 16720 KB Correct.
6 Correct 24 ms 8528 KB Correct.
7 Correct 40 ms 7440 KB Correct.
8 Correct 44 ms 3020 KB Correct.
9 Correct 20 ms 1792 KB Correct.
10 Correct 20 ms 1724 KB Correct.
11 Correct 43 ms 2592 KB Correct.
12 Correct 23 ms 2084 KB Correct.
13 Correct 21 ms 1828 KB Correct.
14 Correct 45 ms 9280 KB Correct.
15 Correct 48 ms 4412 KB Correct.
16 Correct 21 ms 1852 KB Correct.
17 Correct 22 ms 1872 KB Correct.
18 Correct 22 ms 1888 KB Correct.
19 Correct 43 ms 2796 KB Correct.
20 Correct 3 ms 600 KB Correct.
21 Correct 3 ms 760 KB Correct.
22 Correct 4 ms 1116 KB Correct.

Subtask #8
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 1068 KB Correct.
2 Correct 4 ms 1624 KB Correct.
3 Correct 67 ms 67548 KB Correct.
4 Correct 47 ms 4440 KB Correct.
5 Correct 43 ms 27680 KB Correct.
6 Correct 25 ms 11868 KB Correct.
7 Correct 44 ms 13148 KB Correct.
8 Correct 51 ms 3032 KB Correct.
9 Correct 24 ms 2208 KB Correct.
10 Correct 23 ms 2028 KB Correct.
11 Correct 183 ms 1668 KB Correct.
12 Correct 28 ms 2604 KB Correct.
13 Correct 30 ms 2076 KB Correct.
14 Correct 50 ms 27988 KB Correct.
15 Correct 53 ms 34596 KB Correct.
16 Correct 43 ms 12664 KB Correct.
17 Correct 43 ms 4324 KB Correct.
18 Correct 25 ms 2080 KB Correct.
19 Correct 27 ms 2252 KB Correct.
20 Correct 26 ms 2188 KB Correct.
21 Correct 60 ms 3076 KB Correct.
22 Correct 3 ms 604 KB Correct.
23 Correct 3 ms 1016 KB Correct.
24 Correct 4 ms 1368 KB Correct.