Submission #806391

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
806391	2023-08-04T06:29:04 Z	irmuun	Cyberland (APIO23_cyberland)	C++17	100 / 100	189 ms	67532 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	468 KB	Correct.
2	Correct	22 ms	704 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	724 KB	Correct.
2	Correct	22 ms	720 KB	Correct.
3	Correct	21 ms	728 KB	Correct.
4	Correct	24 ms	716 KB	Correct.
5	Correct	22 ms	752 KB	Correct.
6	Correct	19 ms	3724 KB	Correct.
7	Correct	25 ms	3596 KB	Correct.
8	Correct	14 ms	7124 KB	Correct.
9	Correct	22 ms	516 KB	Correct.
10	Correct	22 ms	504 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	700 KB	Correct.
2	Correct	21 ms	704 KB	Correct.
3	Correct	19 ms	768 KB	Correct.
4	Correct	22 ms	468 KB	Correct.
5	Correct	22 ms	468 KB	Correct.
6	Correct	4 ms	3108 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	20104 KB	Correct.
2	Correct	20 ms	1732 KB	Correct.
3	Correct	19 ms	1704 KB	Correct.
4	Correct	19 ms	1696 KB	Correct.
5	Correct	22 ms	1392 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	716 KB	Correct.
2	Correct	23 ms	704 KB	Correct.
3	Correct	29 ms	752 KB	Correct.
4	Correct	22 ms	3488 KB	Correct.
5	Correct	21 ms	468 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	708 KB	Correct.
2	Correct	18 ms	724 KB	Correct.
3	Correct	42 ms	26504 KB	Correct.
4	Correct	14 ms	2416 KB	Correct.
5	Correct	21 ms	480 KB	Correct.
6	Correct	20 ms	728 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	720 KB	Correct.
2	Correct	4 ms	980 KB	Correct.
3	Correct	46 ms	25848 KB	Correct.
4	Correct	41 ms	8456 KB	Correct.
5	Correct	40 ms	16584 KB	Correct.
6	Correct	26 ms	8520 KB	Correct.
7	Correct	41 ms	7368 KB	Correct.
8	Correct	42 ms	2900 KB	Correct.
9	Correct	20 ms	1632 KB	Correct.
10	Correct	21 ms	1588 KB	Correct.
11	Correct	46 ms	2584 KB	Correct.
12	Correct	21 ms	1760 KB	Correct.
13	Correct	21 ms	1732 KB	Correct.
14	Correct	45 ms	9156 KB	Correct.
15	Correct	41 ms	4356 KB	Correct.
16	Correct	21 ms	1784 KB	Correct.
17	Correct	22 ms	1776 KB	Correct.
18	Correct	26 ms	1728 KB	Correct.
19	Correct	45 ms	2664 KB	Correct.
20	Correct	3 ms	544 KB	Correct.
21	Correct	3 ms	692 KB	Correct.
22	Correct	3 ms	1080 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	1012 KB	Correct.
2	Correct	4 ms	1476 KB	Correct.
3	Correct	64 ms	67532 KB	Correct.
4	Correct	40 ms	4424 KB	Correct.
5	Correct	38 ms	27480 KB	Correct.
6	Correct	25 ms	11668 KB	Correct.
7	Correct	44 ms	13208 KB	Correct.
8	Correct	49 ms	3008 KB	Correct.
9	Correct	29 ms	1956 KB	Correct.
10	Correct	23 ms	1880 KB	Correct.
11	Correct	189 ms	1612 KB	Correct.
12	Correct	26 ms	1996 KB	Correct.
13	Correct	24 ms	1992 KB	Correct.
14	Correct	49 ms	27904 KB	Correct.
15	Correct	54 ms	34540 KB	Correct.
16	Correct	44 ms	12572 KB	Correct.
17	Correct	42 ms	4388 KB	Correct.
18	Correct	27 ms	1964 KB	Correct.
19	Correct	29 ms	1980 KB	Correct.
20	Correct	26 ms	1960 KB	Correct.
21	Correct	56 ms	2972 KB	Correct.
22	Correct	4 ms	580 KB	Correct.
23	Correct	3 ms	884 KB	Correct.
24	Correct	3 ms	1492 KB	Correct.

Submission #806391

Compilation message