Submission #750851

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
750851	2023-05-30T11:48:28 Z	josanneo22	Cyberland (APIO23_cyberland)	C++17	100 / 100	262 ms	64988 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	27 ms	468 KB	Correct.
2	Correct	28 ms	436 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	728 KB	Correct.
2	Correct	26 ms	700 KB	Correct.
3	Correct	26 ms	728 KB	Correct.
4	Correct	29 ms	688 KB	Correct.
5	Correct	29 ms	728 KB	Correct.
6	Correct	28 ms	3636 KB	Correct.
7	Correct	29 ms	3668 KB	Correct.
8	Correct	12 ms	7140 KB	Correct.
9	Correct	26 ms	504 KB	Correct.
10	Correct	26 ms	468 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	660 KB	Correct.
2	Correct	25 ms	696 KB	Correct.
3	Correct	25 ms	752 KB	Correct.
4	Correct	30 ms	496 KB	Correct.
5	Correct	26 ms	468 KB	Correct.
6	Correct	5 ms	3028 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	20172 KB	Correct.
2	Correct	26 ms	688 KB	Correct.
3	Correct	23 ms	784 KB	Correct.
4	Correct	23 ms	668 KB	Correct.
5	Correct	27 ms	496 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	672 KB	Correct.
2	Correct	27 ms	656 KB	Correct.
3	Correct	26 ms	708 KB	Correct.
4	Correct	26 ms	3552 KB	Correct.
5	Correct	24 ms	468 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	680 KB	Correct.
2	Correct	22 ms	732 KB	Correct.
3	Correct	55 ms	26496 KB	Correct.
4	Correct	17 ms	2336 KB	Correct.
5	Correct	32 ms	492 KB	Correct.
6	Correct	29 ms	696 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	708 KB	Correct.
2	Correct	4 ms	852 KB	Correct.
3	Correct	56 ms	23532 KB	Correct.
4	Correct	50 ms	6192 KB	Correct.
5	Correct	47 ms	14816 KB	Correct.
6	Correct	29 ms	7000 KB	Correct.
7	Correct	48 ms	6232 KB	Correct.
8	Correct	49 ms	1468 KB	Correct.
9	Correct	24 ms	712 KB	Correct.
10	Correct	29 ms	684 KB	Correct.
11	Correct	53 ms	720 KB	Correct.
12	Correct	26 ms	736 KB	Correct.
13	Correct	25 ms	812 KB	Correct.
14	Correct	61 ms	7636 KB	Correct.
15	Correct	45 ms	2316 KB	Correct.
16	Correct	24 ms	700 KB	Correct.
17	Correct	26 ms	756 KB	Correct.
18	Correct	25 ms	720 KB	Correct.
19	Correct	50 ms	652 KB	Correct.
20	Correct	3 ms	468 KB	Correct.
21	Correct	2 ms	624 KB	Correct.
22	Correct	4 ms	980 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	1028 KB	Correct.
2	Correct	4 ms	1364 KB	Correct.
3	Correct	86 ms	64988 KB	Correct.
4	Correct	63 ms	2752 KB	Correct.
5	Correct	48 ms	25676 KB	Correct.
6	Correct	33 ms	10204 KB	Correct.
7	Correct	54 ms	12500 KB	Correct.
8	Correct	53 ms	1348 KB	Correct.
9	Correct	28 ms	1004 KB	Correct.
10	Correct	27 ms	988 KB	Correct.
11	Correct	262 ms	496 KB	Correct.
12	Correct	30 ms	992 KB	Correct.
13	Correct	28 ms	1004 KB	Correct.
14	Correct	67 ms	26392 KB	Correct.
15	Correct	81 ms	32560 KB	Correct.
16	Correct	56 ms	11100 KB	Correct.
17	Correct	59 ms	2716 KB	Correct.
18	Correct	30 ms	972 KB	Correct.
19	Correct	31 ms	1008 KB	Correct.
20	Correct	29 ms	1012 KB	Correct.
21	Correct	58 ms	964 KB	Correct.
22	Correct	3 ms	468 KB	Correct.
23	Correct	3 ms	884 KB	Correct.
24	Correct	4 ms	1236 KB	Correct.

Submission #750851

Compilation message