Submission #1050889

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1050889	2024-08-09T16:18:35 Z	vjudge1	Cyberland (APIO23_cyberland)	C++17	100 / 100	262 ms	169668 KB

cyberland

#include "cyberland.h"

#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define ar array
const int N = 2e5 + 20;

namespace DSU{
	int p[N];
	void init(int n){
		iota(p, p + n + 1, 0);
	}
	int find(int x){
		if(p[x] == x)return x;
		return p[x] = find(p[x]);
	}
	bool join(int u,int v){
		u = find(u), v = find(v);
		if(u == v)return 0;
		p[u] = v;
		return 1;
	}
};
ld dist[N][100];
priority_queue<pair<ld, ar<int, 2> >, vector<pair<ld, ar<int, 2>>>, greater<pair<ld, ar<int, 2>>>> pq;

void push(int k,int x, ld d){
	if(dist[x][k] > d){
		dist[x][k] = d;
		pq.push({d, {x, k}});
	}
}

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> A) {
	vector<ar<int, 2>> g[n];;
	K = min(K, 69);
	DSU::init(n);
	for(int i = 0;i < m;i++){
		if(x[i] != h && y[i] != h)DSU::join(x[i], y[i]);
		g[x[i]].push_back({y[i], c[i]});
		g[y[i]].push_back({x[i], c[i]});
	}
	ld pow[K + 1];
	pow[0] = 1;
	for(int i = 1;i <= K;i++)pow[i] = pow[i - 1] / 2;
	A[0] = 0;
	pq = priority_queue<pair<ld, ar<int, 2> >, vector<pair<ld, ar<int, 2>>>, greater<pair<ld, ar<int, 2>>>>();
	for(int i = 0;i < n;i++){
		for(int j = 0;j <= K;j++){
			dist[i][j] = 1e18;
		}
	}
	push(K, h, 0);
	while(pq.size()){
		ld d = pq.top().first;
		auto [x, k] = pq.top().second;
		pq.pop();
		if(dist[x][k] < d)continue;
		if(A[x] == 0)return d;
		for(auto [u, c]: g[x]){
			if(DSU::find(u) != DSU::find(0))continue;
			push(k, u, d + c * pow[K - k]);
			if(A[x] == 2 && k > 0)push(k - 1, u, d + c * pow[K - k + 1]);
		}
	}
    return -1;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	604 KB	Correct.
2	Correct	13 ms	836 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	2652 KB	Correct.
2	Correct	21 ms	2652 KB	Correct.
3	Correct	20 ms	2652 KB	Correct.
4	Correct	26 ms	2804 KB	Correct.
5	Correct	21 ms	2652 KB	Correct.
6	Correct	20 ms	17752 KB	Correct.
7	Correct	22 ms	17756 KB	Correct.
8	Correct	11 ms	33116 KB	Correct.
9	Correct	19 ms	604 KB	Correct.
10	Correct	19 ms	604 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	2652 KB	Correct.
2	Correct	20 ms	3676 KB	Correct.
3	Correct	18 ms	3724 KB	Correct.
4	Correct	20 ms	1548 KB	Correct.
5	Correct	19 ms	1404 KB	Correct.
6	Correct	5 ms	15708 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	97372 KB	Correct.
2	Correct	26 ms	3672 KB	Correct.
3	Correct	21 ms	3704 KB	Correct.
4	Correct	19 ms	3672 KB	Correct.
5	Correct	23 ms	1420 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	2904 KB	Correct.
2	Correct	23 ms	2652 KB	Correct.
3	Correct	22 ms	2828 KB	Correct.
4	Correct	21 ms	18180 KB	Correct.
5	Correct	19 ms	604 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	2800 KB	Correct.
2	Correct	18 ms	3676 KB	Correct.
3	Correct	57 ms	127708 KB	Correct.
4	Correct	15 ms	14168 KB	Correct.
5	Correct	27 ms	1372 KB	Correct.
6	Correct	22 ms	3676 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	2800 KB	Correct.
2	Correct	3 ms	4956 KB	Correct.
3	Correct	62 ms	160496 KB	Correct.
4	Correct	35 ms	39764 KB	Correct.
5	Correct	34 ms	65360 KB	Correct.
6	Correct	19 ms	22608 KB	Correct.
7	Correct	39 ms	43856 KB	Correct.
8	Correct	36 ms	9036 KB	Correct.
9	Correct	20 ms	3676 KB	Correct.
10	Correct	19 ms	3676 KB	Correct.
11	Correct	37 ms	4684 KB	Correct.
12	Correct	22 ms	3676 KB	Correct.
13	Correct	20 ms	3808 KB	Correct.
14	Correct	41 ms	78628 KB	Correct.
15	Correct	33 ms	24312 KB	Correct.
16	Correct	21 ms	3928 KB	Correct.
17	Correct	22 ms	3712 KB	Correct.
18	Correct	21 ms	3672 KB	Correct.
19	Correct	40 ms	4676 KB	Correct.
20	Correct	3 ms	600 KB	Correct.
21	Correct	3 ms	2652 KB	Correct.
22	Correct	2 ms	3164 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	2856 KB	Correct.
2	Correct	4 ms	4952 KB	Correct.
3	Correct	116 ms	169668 KB	Correct.
4	Correct	36 ms	13404 KB	Correct.
5	Correct	38 ms	65364 KB	Correct.
6	Correct	20 ms	22620 KB	Correct.
7	Correct	49 ms	61672 KB	Correct.
8	Correct	44 ms	4944 KB	Correct.
9	Correct	28 ms	3804 KB	Correct.
10	Correct	28 ms	3600 KB	Correct.
11	Correct	262 ms	1876 KB	Correct.
12	Correct	32 ms	3676 KB	Correct.
13	Correct	30 ms	3860 KB	Correct.
14	Correct	50 ms	66324 KB	Correct.
15	Correct	58 ms	84048 KB	Correct.
16	Correct	39 ms	32904 KB	Correct.
17	Correct	39 ms	9044 KB	Correct.
18	Correct	33 ms	3904 KB	Correct.
19	Correct	31 ms	3916 KB	Correct.
20	Correct	31 ms	3856 KB	Correct.
21	Correct	58 ms	4688 KB	Correct.
22	Correct	4 ms	604 KB	Correct.
23	Correct	4 ms	2768 KB	Correct.
24	Correct	2 ms	3164 KB	Correct.

Submission #1050889

Compilation message