Submission #985361

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
985361	2024-05-17T16:44:18 Z	CrazyBotBoy	Cyberland (APIO23_cyberland)	C++17	100 / 100	183 ms	67548 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	21 ms	604 KB	Correct.
2	Correct	22 ms	860 KB	Correct.

Subtask #2
8.0 / 8.0

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

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

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

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

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

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

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

Submission #985361

Compilation message