Submission #881070

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
881070	2023-11-30T14:08:03 Z	user314	Cyberland (APIO23_cyberland)	C++17	100 / 100	201 ms	67660 KB

cyberland

#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

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	860 KB	Correct.
2	Correct	28 ms	876 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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.

Submission #881070

Compilation message