Submission #985737

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
985737	2024-05-18T15:21:02 Z	siewjh	Cyberland (APIO23_cyberland)	C++17	100 / 100	395 ms	120356 KB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef tuple<ld, int, int> t3;
const int MAXN = 100005;
const ld inf = 1e18;
vector<pair<int, int>> adj[MAXN];
bool vis[MAXN], conn[MAXN];
ld dist[MAXN][70], pwr[70];

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){
	K = min(K, 68);
	pwr[0] = 1;
	for (int i = 1; i <= 68; i++) pwr[i] = pwr[i - 1] / 2;
	for (int i = 0; i < N; i++){
		adj[i].clear(); vis[i] = 0; conn[i] = 0;
		for (int j = 0; j <= K; j++) dist[i][j] = inf;
	}
	for (int i = 0; i < M; i++){
		adj[x[i]].push_back({y[i], c[i]});
		adj[y[i]].push_back({x[i], c[i]});
	}
	queue<int> q;
	q.push(0); vis[0] = 1; conn[0] = 1;
	while (!q.empty()){
		int x = q.front(); q.pop();
		if (x == H) continue;
		if (arr[x] == 0) conn[x] = 1;
		for (auto &[nn, nd] : adj[x])
			if (!vis[nn]){
				q.push(nn); vis[nn] = 1;
			}
	}
	priority_queue<t3, vector<t3>, greater<t3>> pq;
	pq.push({0, H, 0}); dist[H][0] = 0;
	while (!pq.empty()){
		ld d; int x, use; tie(d, x, use) = pq.top(); pq.pop();
		if (dist[x][use] < d) continue;
		if (x == H && use != 0) continue;
		if (conn[x]) return d;
		for (auto &[nn, nd] : adj[x]){
			ld fd = d + nd * pwr[use];
			if (dist[nn][use] > fd){
				dist[nn][use] = fd;
				pq.push({dist[nn][use], nn, use});
			}
			if (arr[nn] == 2 && use < K && dist[nn][use + 1] > fd){
				dist[nn][use + 1] = fd;
				pq.push({dist[nn][use + 1], nn, use + 1});
			}
		}
	}
	return -1;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	3676 KB	Correct.
2	Correct	19 ms	3928 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	5976 KB	Correct.
2	Correct	24 ms	5976 KB	Correct.
3	Correct	23 ms	5964 KB	Correct.
4	Correct	24 ms	5976 KB	Correct.
5	Correct	24 ms	6008 KB	Correct.
6	Correct	28 ms	16732 KB	Correct.
7	Correct	30 ms	16732 KB	Correct.
8	Correct	15 ms	27740 KB	Correct.
9	Correct	24 ms	3676 KB	Correct.
10	Correct	24 ms	3808 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	5980 KB	Correct.
2	Correct	22 ms	5980 KB	Correct.
3	Correct	22 ms	5976 KB	Correct.
4	Correct	24 ms	3676 KB	Correct.
5	Correct	27 ms	3676 KB	Correct.
6	Correct	7 ms	14428 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	73040 KB	Correct.
2	Correct	33 ms	5980 KB	Correct.
3	Correct	34 ms	6740 KB	Correct.
4	Correct	33 ms	6740 KB	Correct.
5	Correct	45 ms	4440 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	5976 KB	Correct.
2	Correct	28 ms	5976 KB	Correct.
3	Correct	26 ms	5980 KB	Correct.
4	Correct	28 ms	16864 KB	Correct.
5	Correct	24 ms	3820 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	5980 KB	Correct.
2	Correct	23 ms	6312 KB	Correct.
3	Correct	54 ms	93092 KB	Correct.
4	Correct	17 ms	12636 KB	Correct.
5	Correct	24 ms	3676 KB	Correct.
6	Correct	22 ms	6028 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	5980 KB	Correct.
2	Correct	11 ms	6236 KB	Correct.
3	Correct	72 ms	116296 KB	Correct.
4	Correct	48 ms	31352 KB	Correct.
5	Correct	40 ms	48464 KB	Correct.
6	Correct	26 ms	21076 KB	Correct.
7	Correct	46 ms	33392 KB	Correct.
8	Correct	43 ms	9448 KB	Correct.
9	Correct	43 ms	6776 KB	Correct.
10	Correct	45 ms	6748 KB	Correct.
11	Correct	46 ms	7260 KB	Correct.
12	Correct	60 ms	6784 KB	Correct.
13	Correct	44 ms	6836 KB	Correct.
14	Correct	49 ms	59148 KB	Correct.
15	Correct	45 ms	20312 KB	Correct.
16	Correct	45 ms	6732 KB	Correct.
17	Correct	45 ms	6736 KB	Correct.
18	Correct	34 ms	6764 KB	Correct.
19	Correct	124 ms	7248 KB	Correct.
20	Correct	5 ms	3932 KB	Correct.
21	Correct	6 ms	5980 KB	Correct.
22	Correct	4 ms	6484 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	51 ms	5976 KB	Correct.
2	Correct	21 ms	6232 KB	Correct.
3	Correct	124 ms	120356 KB	Correct.
4	Correct	42 ms	13908 KB	Correct.
5	Correct	45 ms	48468 KB	Correct.
6	Correct	28 ms	21584 KB	Correct.
7	Correct	49 ms	47800 KB	Correct.
8	Correct	51 ms	7992 KB	Correct.
9	Correct	77 ms	7320 KB	Correct.
10	Correct	83 ms	7164 KB	Correct.
11	Correct	395 ms	4940 KB	Correct.
12	Correct	98 ms	7152 KB	Correct.
13	Correct	63 ms	6984 KB	Correct.
14	Correct	55 ms	52704 KB	Correct.
15	Correct	63 ms	64608 KB	Correct.
16	Correct	49 ms	27780 KB	Correct.
17	Correct	46 ms	10028 KB	Correct.
18	Correct	83 ms	7168 KB	Correct.
19	Correct	74 ms	7004 KB	Correct.
20	Correct	56 ms	7056 KB	Correct.
21	Correct	242 ms	7940 KB	Correct.
22	Correct	7 ms	3932 KB	Correct.
23	Correct	10 ms	6116 KB	Correct.
24	Correct	4 ms	6236 KB	Correct.

Submission #985737

Compilation message