Submission #752298

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
752298	2023-06-02T16:59:27 Z	YassineBenYounes	Cyberland (APIO23_cyberland)	C++17	100 / 100	266 ms	65048 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	29 ms	468 KB	Correct.
2	Correct	28 ms	460 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	732 KB	Correct.
2	Correct	28 ms	688 KB	Correct.
3	Correct	26 ms	672 KB	Correct.
4	Correct	27 ms	688 KB	Correct.
5	Correct	27 ms	712 KB	Correct.
6	Correct	23 ms	3652 KB	Correct.
7	Correct	30 ms	3616 KB	Correct.
8	Correct	13 ms	7152 KB	Correct.
9	Correct	28 ms	468 KB	Correct.
10	Correct	29 ms	612 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	684 KB	Correct.
2	Correct	25 ms	732 KB	Correct.
3	Correct	26 ms	728 KB	Correct.
4	Correct	27 ms	508 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	34 ms	20172 KB	Correct.
2	Correct	24 ms	708 KB	Correct.
3	Correct	22 ms	792 KB	Correct.
4	Correct	26 ms	668 KB	Correct.
5	Correct	31 ms	516 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	720 KB	Correct.
2	Correct	28 ms	684 KB	Correct.
3	Correct	29 ms	780 KB	Correct.
4	Correct	27 ms	3488 KB	Correct.
5	Correct	25 ms	468 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	728 KB	Correct.
2	Correct	21 ms	756 KB	Correct.
3	Correct	55 ms	26420 KB	Correct.
4	Correct	17 ms	2352 KB	Correct.
5	Correct	28 ms	412 KB	Correct.
6	Correct	25 ms	704 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	776 KB	Correct.
2	Correct	3 ms	852 KB	Correct.
3	Correct	57 ms	23536 KB	Correct.
4	Correct	54 ms	6188 KB	Correct.
5	Correct	45 ms	14708 KB	Correct.
6	Correct	31 ms	6988 KB	Correct.
7	Correct	50 ms	6216 KB	Correct.
8	Correct	55 ms	1348 KB	Correct.
9	Correct	25 ms	712 KB	Correct.
10	Correct	26 ms	716 KB	Correct.
11	Correct	61 ms	736 KB	Correct.
12	Correct	27 ms	724 KB	Correct.
13	Correct	25 ms	740 KB	Correct.
14	Correct	51 ms	7636 KB	Correct.
15	Correct	49 ms	2344 KB	Correct.
16	Correct	25 ms	696 KB	Correct.
17	Correct	35 ms	912 KB	Correct.
18	Correct	26 ms	768 KB	Correct.
19	Correct	55 ms	652 KB	Correct.
20	Correct	3 ms	468 KB	Correct.
21	Correct	2 ms	616 KB	Correct.
22	Correct	3 ms	980 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	968 KB	Correct.
2	Correct	4 ms	1364 KB	Correct.
3	Correct	80 ms	65048 KB	Correct.
4	Correct	50 ms	2760 KB	Correct.
5	Correct	49 ms	25676 KB	Correct.
6	Correct	32 ms	10196 KB	Correct.
7	Correct	53 ms	12500 KB	Correct.
8	Correct	55 ms	1372 KB	Correct.
9	Correct	27 ms	1092 KB	Correct.
10	Correct	27 ms	980 KB	Correct.
11	Correct	266 ms	624 KB	Correct.
12	Correct	30 ms	1040 KB	Correct.
13	Correct	29 ms	996 KB	Correct.
14	Correct	65 ms	26492 KB	Correct.
15	Correct	64 ms	32556 KB	Correct.
16	Correct	52 ms	11128 KB	Correct.
17	Correct	51 ms	2740 KB	Correct.
18	Correct	30 ms	976 KB	Correct.
19	Correct	32 ms	1044 KB	Correct.
20	Correct	31 ms	1172 KB	Correct.
21	Correct	58 ms	972 KB	Correct.
22	Correct	4 ms	468 KB	Correct.
23	Correct	3 ms	884 KB	Correct.
24	Correct	4 ms	1236 KB	Correct.

Submission #752298

Compilation message