Submission #969031

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
969031	2024-04-24T11:56:22 Z	kshitiz101	Cyberland (APIO23_cyberland)	C++17	100 / 100	180 ms	67668 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	860 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	1732 KB	Correct.
2	Correct	23 ms	1816 KB	Correct.
3	Correct	21 ms	1836 KB	Correct.
4	Correct	22 ms	1844 KB	Correct.
5	Correct	22 ms	1904 KB	Correct.
6	Correct	22 ms	4684 KB	Correct.
7	Correct	26 ms	4392 KB	Correct.
8	Correct	11 ms	7772 KB	Correct.
9	Correct	22 ms	1396 KB	Correct.
10	Correct	22 ms	1372 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	1796 KB	Correct.
2	Correct	21 ms	1776 KB	Correct.
3	Correct	19 ms	1764 KB	Correct.
4	Correct	22 ms	1372 KB	Correct.
5	Correct	25 ms	1372 KB	Correct.
6	Correct	5 ms	3420 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	21452 KB	Correct.
2	Correct	20 ms	1816 KB	Correct.
3	Correct	19 ms	1832 KB	Correct.
4	Correct	20 ms	1832 KB	Correct.
5	Correct	22 ms	1372 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	1676 KB	Correct.
2	Correct	24 ms	1856 KB	Correct.
3	Correct	23 ms	1900 KB	Correct.
4	Correct	26 ms	4136 KB	Correct.
5	Correct	21 ms	1372 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	1804 KB	Correct.
2	Correct	19 ms	1720 KB	Correct.
3	Correct	44 ms	28356 KB	Correct.
4	Correct	14 ms	3064 KB	Correct.
5	Correct	22 ms	1372 KB	Correct.
6	Correct	20 ms	1736 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	1832 KB	Correct.
2	Correct	3 ms	1116 KB	Correct.
3	Correct	48 ms	25936 KB	Correct.
4	Correct	42 ms	8584 KB	Correct.
5	Correct	35 ms	16732 KB	Correct.
6	Correct	25 ms	8532 KB	Correct.
7	Correct	41 ms	7452 KB	Correct.
8	Correct	41 ms	2964 KB	Correct.
9	Correct	20 ms	1872 KB	Correct.
10	Correct	20 ms	1724 KB	Correct.
11	Correct	43 ms	2592 KB	Correct.
12	Correct	22 ms	1828 KB	Correct.
13	Correct	21 ms	1796 KB	Correct.
14	Correct	41 ms	9292 KB	Correct.
15	Correct	45 ms	4516 KB	Correct.
16	Correct	21 ms	1804 KB	Correct.
17	Correct	22 ms	1860 KB	Correct.
18	Correct	22 ms	1840 KB	Correct.
19	Correct	42 ms	2792 KB	Correct.
20	Correct	3 ms	604 KB	Correct.
21	Correct	2 ms	764 KB	Correct.
22	Correct	3 ms	1116 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	2000 KB	Correct.
2	Correct	4 ms	1628 KB	Correct.
3	Correct	67 ms	67668 KB	Correct.
4	Correct	42 ms	4436 KB	Correct.
5	Correct	39 ms	27192 KB	Correct.
6	Correct	30 ms	11836 KB	Correct.
7	Correct	44 ms	13148 KB	Correct.
8	Correct	45 ms	3056 KB	Correct.
9	Correct	24 ms	1996 KB	Correct.
10	Correct	24 ms	2176 KB	Correct.
11	Correct	180 ms	1548 KB	Correct.
12	Correct	26 ms	2024 KB	Correct.
13	Correct	25 ms	2160 KB	Correct.
14	Correct	60 ms	27932 KB	Correct.
15	Correct	54 ms	34548 KB	Correct.
16	Correct	42 ms	12652 KB	Correct.
17	Correct	42 ms	4512 KB	Correct.
18	Correct	26 ms	2072 KB	Correct.
19	Correct	26 ms	2300 KB	Correct.
20	Correct	26 ms	2180 KB	Correct.
21	Correct	59 ms	3420 KB	Correct.
22	Correct	3 ms	600 KB	Correct.
23	Correct	3 ms	1016 KB	Correct.
24	Correct	3 ms	1368 KB	Correct.

Submission #969031

Compilation message