oj.uz

답안 #881070

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
881070 2023-11-30T14:08:03 Z user314 사이버랜드 (APIO23_cyberland) C++17
100 / 100
 201 ms 67660 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 22 ms 860 KB Correct.
2 Correct 28 ms 876 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 1712 KB Correct.
2 Correct 22 ms 1836 KB Correct.
3 Correct 21 ms 1844 KB Correct.
4 Correct 22 ms 1820 KB Correct.
5 Correct 22 ms 1836 KB Correct.
6 Correct 24 ms 4672 KB Correct.
7 Correct 25 ms 4388 KB Correct.
8 Correct 11 ms 7772 KB Correct.
9 Correct 28 ms 1372 KB Correct.
10 Correct 22 ms 1368 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 1788 KB Correct.
2 Correct 24 ms 1932 KB Correct.
3 Correct 19 ms 1756 KB Correct.
4 Correct 23 ms 1384 KB Correct.
5 Correct 22 ms 1388 KB Correct.
6 Correct 4 ms 3420 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 21588 KB Correct.
2 Correct 20 ms 1876 KB Correct.
3 Correct 19 ms 1820 KB Correct.
4 Correct 19 ms 1764 KB Correct.
5 Correct 22 ms 1372 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 1748 KB Correct.
2 Correct 24 ms 1836 KB Correct.
3 Correct 23 ms 1776 KB Correct.
4 Correct 22 ms 4136 KB Correct.
5 Correct 21 ms 1384 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 1804 KB Correct.
2 Correct 24 ms 1808 KB Correct.
3 Correct 48 ms 28500 KB Correct.
4 Correct 15 ms 2996 KB Correct.
5 Correct 22 ms 1484 KB Correct.
6 Correct 20 ms 1752 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 1836 KB Correct.
2 Correct 3 ms 1112 KB Correct.
3 Correct 51 ms 25984 KB Correct.
4 Correct 41 ms 8520 KB Correct.
5 Correct 34 ms 16732 KB Correct.
6 Correct 24 ms 8532 KB Correct.
7 Correct 41 ms 7572 KB Correct.
8 Correct 41 ms 2964 KB Correct.
9 Correct 20 ms 1868 KB Correct.
10 Correct 23 ms 1724 KB Correct.
11 Correct 43 ms 2704 KB Correct.
12 Correct 22 ms 1816 KB Correct.
13 Correct 21 ms 1784 KB Correct.
14 Correct 41 ms 9268 KB Correct.
15 Correct 41 ms 4512 KB Correct.
16 Correct 21 ms 1976 KB Correct.
17 Correct 22 ms 1908 KB Correct.
18 Correct 21 ms 1840 KB Correct.
19 Correct 42 ms 2804 KB Correct.
20 Correct 3 ms 604 KB Correct.
21 Correct 2 ms 764 KB Correct.
22 Correct 3 ms 1216 KB Correct.

Subtask #8
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 2008 KB Correct.
2 Correct 4 ms 1480 KB Correct.
3 Correct 69 ms 67660 KB Correct.
4 Correct 40 ms 4444 KB Correct.
5 Correct 39 ms 27476 KB Correct.
6 Correct 31 ms 11852 KB Correct.
7 Correct 45 ms 13148 KB Correct.
8 Correct 54 ms 3260 KB Correct.
9 Correct 24 ms 1992 KB Correct.
10 Correct 23 ms 2028 KB Correct.
11 Correct 201 ms 1720 KB Correct.
12 Correct 29 ms 2084 KB Correct.
13 Correct 25 ms 2156 KB Correct.
14 Correct 52 ms 27984 KB Correct.
15 Correct 65 ms 34560 KB Correct.
16 Correct 44 ms 12652 KB Correct.
17 Correct 42 ms 4456 KB Correct.
18 Correct 33 ms 2116 KB Correct.
19 Correct 26 ms 2216 KB Correct.
20 Correct 28 ms 2240 KB Correct.
21 Correct 51 ms 3080 KB Correct.
22 Correct 3 ms 604 KB Correct.
23 Correct 3 ms 1020 KB Correct.
24 Correct 3 ms 1372 KB Correct.