oj.uz

답안 #806391

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
806391 2023-08-04T06:29:04 Z irmuun 사이버랜드 (APIO23_cyberland) C++17
100 / 100
 189 ms 67532 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 468 KB Correct.
2 Correct 22 ms 704 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 724 KB Correct.
2 Correct 22 ms 720 KB Correct.
3 Correct 21 ms 728 KB Correct.
4 Correct 24 ms 716 KB Correct.
5 Correct 22 ms 752 KB Correct.
6 Correct 19 ms 3724 KB Correct.
7 Correct 25 ms 3596 KB Correct.
8 Correct 14 ms 7124 KB Correct.
9 Correct 22 ms 516 KB Correct.
10 Correct 22 ms 504 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 700 KB Correct.
2 Correct 21 ms 704 KB Correct.
3 Correct 19 ms 768 KB Correct.
4 Correct 22 ms 468 KB Correct.
5 Correct 22 ms 468 KB Correct.
6 Correct 4 ms 3108 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 20104 KB Correct.
2 Correct 20 ms 1732 KB Correct.
3 Correct 19 ms 1704 KB Correct.
4 Correct 19 ms 1696 KB Correct.
5 Correct 22 ms 1392 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 716 KB Correct.
2 Correct 23 ms 704 KB Correct.
3 Correct 29 ms 752 KB Correct.
4 Correct 22 ms 3488 KB Correct.
5 Correct 21 ms 468 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 708 KB Correct.
2 Correct 18 ms 724 KB Correct.
3 Correct 42 ms 26504 KB Correct.
4 Correct 14 ms 2416 KB Correct.
5 Correct 21 ms 480 KB Correct.
6 Correct 20 ms 728 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 720 KB Correct.
2 Correct 4 ms 980 KB Correct.
3 Correct 46 ms 25848 KB Correct.
4 Correct 41 ms 8456 KB Correct.
5 Correct 40 ms 16584 KB Correct.
6 Correct 26 ms 8520 KB Correct.
7 Correct 41 ms 7368 KB Correct.
8 Correct 42 ms 2900 KB Correct.
9 Correct 20 ms 1632 KB Correct.
10 Correct 21 ms 1588 KB Correct.
11 Correct 46 ms 2584 KB Correct.
12 Correct 21 ms 1760 KB Correct.
13 Correct 21 ms 1732 KB Correct.
14 Correct 45 ms 9156 KB Correct.
15 Correct 41 ms 4356 KB Correct.
16 Correct 21 ms 1784 KB Correct.
17 Correct 22 ms 1776 KB Correct.
18 Correct 26 ms 1728 KB Correct.
19 Correct 45 ms 2664 KB Correct.
20 Correct 3 ms 544 KB Correct.
21 Correct 3 ms 692 KB Correct.
22 Correct 3 ms 1080 KB Correct.

Subtask #8
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 1012 KB Correct.
2 Correct 4 ms 1476 KB Correct.
3 Correct 64 ms 67532 KB Correct.
4 Correct 40 ms 4424 KB Correct.
5 Correct 38 ms 27480 KB Correct.
6 Correct 25 ms 11668 KB Correct.
7 Correct 44 ms 13208 KB Correct.
8 Correct 49 ms 3008 KB Correct.
9 Correct 29 ms 1956 KB Correct.
10 Correct 23 ms 1880 KB Correct.
11 Correct 189 ms 1612 KB Correct.
12 Correct 26 ms 1996 KB Correct.
13 Correct 24 ms 1992 KB Correct.
14 Correct 49 ms 27904 KB Correct.
15 Correct 54 ms 34540 KB Correct.
16 Correct 44 ms 12572 KB Correct.
17 Correct 42 ms 4388 KB Correct.
18 Correct 27 ms 1964 KB Correct.
19 Correct 29 ms 1980 KB Correct.
20 Correct 26 ms 1960 KB Correct.
21 Correct 56 ms 2972 KB Correct.
22 Correct 4 ms 580 KB Correct.
23 Correct 3 ms 884 KB Correct.
24 Correct 3 ms 1492 KB Correct.