oj.uz

답안 #969031

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
969031 2024-04-24T11:56:22 Z kshitiz101 사이버랜드 (APIO23_cyberland) C++17
100 / 100
 180 ms 67668 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 860 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 1732 KB Correct.
2 Correct 23 ms 1816 KB Correct.
3 Correct 21 ms 1836 KB Correct.
4 Correct 22 ms 1844 KB Correct.
5 Correct 22 ms 1904 KB Correct.
6 Correct 22 ms 4684 KB Correct.
7 Correct 26 ms 4392 KB Correct.
8 Correct 11 ms 7772 KB Correct.
9 Correct 22 ms 1396 KB Correct.
10 Correct 22 ms 1372 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 1796 KB Correct.
2 Correct 21 ms 1776 KB Correct.
3 Correct 19 ms 1764 KB Correct.
4 Correct 22 ms 1372 KB Correct.
5 Correct 25 ms 1372 KB Correct.
6 Correct 5 ms 3420 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 21452 KB Correct.
2 Correct 20 ms 1816 KB Correct.
3 Correct 19 ms 1832 KB Correct.
4 Correct 20 ms 1832 KB Correct.
5 Correct 22 ms 1372 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 1676 KB Correct.
2 Correct 24 ms 1856 KB Correct.
3 Correct 23 ms 1900 KB Correct.
4 Correct 26 ms 4136 KB Correct.
5 Correct 21 ms 1372 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 1804 KB Correct.
2 Correct 19 ms 1720 KB Correct.
3 Correct 44 ms 28356 KB Correct.
4 Correct 14 ms 3064 KB Correct.
5 Correct 22 ms 1372 KB Correct.
6 Correct 20 ms 1736 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 1832 KB Correct.
2 Correct 3 ms 1116 KB Correct.
3 Correct 48 ms 25936 KB Correct.
4 Correct 42 ms 8584 KB Correct.
5 Correct 35 ms 16732 KB Correct.
6 Correct 25 ms 8532 KB Correct.
7 Correct 41 ms 7452 KB Correct.
8 Correct 41 ms 2964 KB Correct.
9 Correct 20 ms 1872 KB Correct.
10 Correct 20 ms 1724 KB Correct.
11 Correct 43 ms 2592 KB Correct.
12 Correct 22 ms 1828 KB Correct.
13 Correct 21 ms 1796 KB Correct.
14 Correct 41 ms 9292 KB Correct.
15 Correct 45 ms 4516 KB Correct.
16 Correct 21 ms 1804 KB Correct.
17 Correct 22 ms 1860 KB Correct.
18 Correct 22 ms 1840 KB Correct.
19 Correct 42 ms 2792 KB Correct.
20 Correct 3 ms 604 KB Correct.
21 Correct 2 ms 764 KB Correct.
22 Correct 3 ms 1116 KB Correct.

Subtask #8
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 2000 KB Correct.
2 Correct 4 ms 1628 KB Correct.
3 Correct 67 ms 67668 KB Correct.
4 Correct 42 ms 4436 KB Correct.
5 Correct 39 ms 27192 KB Correct.
6 Correct 30 ms 11836 KB Correct.
7 Correct 44 ms 13148 KB Correct.
8 Correct 45 ms 3056 KB Correct.
9 Correct 24 ms 1996 KB Correct.
10 Correct 24 ms 2176 KB Correct.
11 Correct 180 ms 1548 KB Correct.
12 Correct 26 ms 2024 KB Correct.
13 Correct 25 ms 2160 KB Correct.
14 Correct 60 ms 27932 KB Correct.
15 Correct 54 ms 34548 KB Correct.
16 Correct 42 ms 12652 KB Correct.
17 Correct 42 ms 4512 KB Correct.
18 Correct 26 ms 2072 KB Correct.
19 Correct 26 ms 2300 KB Correct.
20 Correct 26 ms 2180 KB Correct.
21 Correct 59 ms 3420 KB Correct.
22 Correct 3 ms 600 KB Correct.
23 Correct 3 ms 1016 KB Correct.
24 Correct 3 ms 1368 KB Correct.