Submission #914127

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
914127	2024-01-21T08:28:36 Z	SmuggingSpun	Cyberland (APIO23_cyberland)	C++17	100 / 100	862 ms	10824 KB

cyberland

#include "cyberland.h"
#include<bits/stdc++.h>
using namespace std;
const double INF = 1e18;
template<class T>void minimize(T& a, T b){
	if(a > b){
		a = b;
	}
}
struct Data{
	int u;
	double w;
	Data(int _u, double _w) : u(_u), w(_w) {}
	friend bool operator <(Data a, Data b){
		return a.w > b.w;
	}
};
double solve(int n, int m, int k, int h, vector<int>x, vector<int>y, vector<int>c, vector<int>arr) {
	vector<vector<pair<int, int>>>e(n);
	for(int i = 0; i < m; i++){
		e[x[i]].emplace_back(y[i], c[i]);
		e[y[i]].emplace_back(x[i], c[i]);
	}
	priority_queue<Data>q;
	vector<double>d(n, INF);
	q.emplace(0, d[0] = 0.0);
	double ans = INF;
	for(int i = min(k, 80); i > -1; i--){
		vector<double>D(n, INF);
		priority_queue<Data>Q;
		while(!q.empty()){
			auto [u, w] = q.top();
			q.pop();
			if(w > d[u] || u == h){
				continue;
			}
			for(auto& [v, weight] : e[u]){
				if(arr[v] == 0){
					if(d[v] > 0.0){
						q.emplace(v, d[v] = 0.0);
					}
				}
				else{
					double W = w + double(weight);
					if(W < d[v]){
						q.emplace(v, d[v] = W);
					}
					if(arr[v] == 2 && i > 0 && (W /= 2.0) < D[v]){
						Q.emplace(v, D[v] = W);
					}
				}
			}
		}
		minimize(ans, d[h]);
		d = D;
		q = Q;
	}
	return ans == INF ? -1 : ans;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	604 KB	Correct.
2	Correct	26 ms	604 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	600 KB	Correct.
2	Correct	22 ms	592 KB	Correct.
3	Correct	21 ms	604 KB	Correct.
4	Correct	22 ms	604 KB	Correct.
5	Correct	23 ms	600 KB	Correct.
6	Correct	18 ms	1436 KB	Correct.
7	Correct	23 ms	1440 KB	Correct.
8	Correct	10 ms	2652 KB	Correct.
9	Correct	29 ms	348 KB	Correct.
10	Correct	21 ms	348 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	600 KB	Correct.
2	Correct	23 ms	348 KB	Correct.
3	Correct	22 ms	604 KB	Correct.
4	Correct	24 ms	348 KB	Correct.
5	Correct	24 ms	348 KB	Correct.
6	Correct	5 ms	1116 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	78 ms	6756 KB	Correct.
2	Correct	78 ms	612 KB	Correct.
3	Correct	69 ms	876 KB	Correct.
4	Correct	73 ms	592 KB	Correct.
5	Correct	57 ms	348 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	600 KB	Correct.
2	Correct	22 ms	348 KB	Correct.
3	Correct	21 ms	604 KB	Correct.
4	Correct	20 ms	1116 KB	Correct.
5	Correct	20 ms	348 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	600 KB	Correct.
2	Correct	20 ms	600 KB	Correct.
3	Correct	34 ms	8540 KB	Correct.
4	Correct	13 ms	1204 KB	Correct.
5	Correct	27 ms	348 KB	Correct.
6	Correct	21 ms	600 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	828 KB	Correct.
2	Correct	15 ms	600 KB	Correct.
3	Correct	294 ms	10824 KB	Correct.
4	Correct	197 ms	2564 KB	Correct.
5	Correct	325 ms	7728 KB	Correct.
6	Correct	150 ms	5432 KB	Correct.
7	Correct	205 ms	2820 KB	Correct.
8	Correct	156 ms	848 KB	Correct.
9	Correct	75 ms	604 KB	Correct.
10	Correct	76 ms	592 KB	Correct.
11	Correct	148 ms	912 KB	Correct.
12	Correct	84 ms	596 KB	Correct.
13	Correct	82 ms	592 KB	Correct.
14	Correct	189 ms	5568 KB	Correct.
15	Correct	180 ms	1604 KB	Correct.
16	Correct	84 ms	592 KB	Correct.
17	Correct	95 ms	592 KB	Correct.
18	Correct	92 ms	596 KB	Correct.
19	Correct	245 ms	348 KB	Correct.
20	Correct	5 ms	348 KB	Correct.
21	Correct	6 ms	528 KB	Correct.
22	Correct	12 ms	860 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	194 ms	596 KB	Correct.
2	Correct	36 ms	604 KB	Correct.
3	Correct	112 ms	10620 KB	Correct.
4	Correct	230 ms	1104 KB	Correct.
5	Correct	786 ms	7876 KB	Correct.
6	Correct	364 ms	5592 KB	Correct.
7	Correct	381 ms	5312 KB	Correct.
8	Correct	196 ms	2564 KB	Correct.
9	Correct	152 ms	1348 KB	Correct.
10	Correct	154 ms	1344 KB	Correct.
11	Correct	128 ms	1620 KB	Correct.
12	Correct	174 ms	1616 KB	Correct.
13	Correct	169 ms	1560 KB	Correct.
14	Correct	862 ms	7592 KB	Correct.
15	Correct	675 ms	7828 KB	Correct.
16	Correct	311 ms	4120 KB	Correct.
17	Correct	229 ms	2700 KB	Correct.
18	Correct	167 ms	1404 KB	Correct.
19	Correct	199 ms	1616 KB	Correct.
20	Correct	188 ms	1616 KB	Correct.
21	Correct	569 ms	2384 KB	Correct.
22	Correct	10 ms	348 KB	Correct.
23	Correct	13 ms	348 KB	Correct.
24	Correct	28 ms	1116 KB	Correct.

Submission #914127

Compilation message