Submission #982090

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
982090	2024-05-13T19:19:28 Z	vjudge1	Cyberland (APIO23_cyberland)	C++17	100 / 100	1185 ms	15492 KB

cyberland

// hola soy Dember :D
// 31/03/2024

#include <bits/stdc++.h>
#define dd double

using namespace std;

const dd inf=1e18;

dd solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> a) {
	k=min(k, 100);
	vector<vector<pair<int, dd>>> v(n);
	for(int i=0; i<m; i++){
		v[x[i]].push_back({y[i], c[i]});
		v[y[i]].push_back({x[i], c[i]});
	}
	
	vector<double> dp(n), tt(n); 
	for(auto &p:dp) p=inf;
	for(auto &p:tt) p=inf;
	
	priority_queue<pair<dd, int>> q;
	tt[0]=0.;
    dd ans=1e18;
    
	for(int j=0; j<=k; j++){
		vector<double> tt(n); for(double &p:tt) p=inf;
		if(j){
			for(int i=0; i<n; i++){
				if(a[i]==1 || dp[i]==inf) continue;
				if(a[i]==0)tt[i]=0;
				q.push({-dp[i]/2., i});
			}
		} else q.push({0., 0});
		
		while(!q.empty()) {
			auto [cur, u]=q.top(); cur=-cur;
			q.pop();
			if(u==h) continue;
			for(auto [v, w]:v[u]) {
				if(tt[v]>cur+w) {
					if(a[v]==0) tt[v]=0.;
					else tt[v]=cur+w;
					q.push({-tt[v], v});
				}
			}
		}
		ans=min(ans, tt[h]);
		if(j==0 && tt[h]==inf) break;
		swap(tt, dp);
	}
	return ((ans<inf)? ans: -1.);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	604 KB	Correct.
2	Correct	29 ms	1872 KB	Correct.
3	Correct	23 ms	1616 KB	Correct.
4	Correct	24 ms	1624 KB	Correct.
5	Correct	25 ms	1488 KB	Correct.
6	Correct	22 ms	2476 KB	Correct.
7	Correct	39 ms	2724 KB	Correct.
8	Correct	11 ms	3464 KB	Correct.
9	Correct	31 ms	1412 KB	Correct.
10	Correct	23 ms	1384 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	142 ms	576 KB	Correct.
2	Correct	129 ms	1376 KB	Correct.
3	Correct	114 ms	1372 KB	Correct.
4	Correct	71 ms	1376 KB	Correct.
5	Correct	70 ms	1372 KB	Correct.
6	Correct	37 ms	1640 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	125 ms	8140 KB	Correct.
2	Correct	111 ms	1640 KB	Correct.
3	Correct	95 ms	1624 KB	Correct.
4	Correct	101 ms	1612 KB	Correct.
5	Correct	57 ms	1456 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	616 KB	Correct.
2	Correct	23 ms	1616 KB	Correct.
3	Correct	22 ms	1640 KB	Correct.
4	Correct	20 ms	2380 KB	Correct.
5	Correct	19 ms	1380 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	78 ms	1372 KB	Correct.
2	Correct	49 ms	1368 KB	Correct.
3	Correct	33 ms	12384 KB	Correct.
4	Correct	63 ms	2144 KB	Correct.
5	Correct	43 ms	1380 KB	Correct.
6	Correct	59 ms	1372 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	112 ms	1236 KB	Correct.
2	Correct	17 ms	608 KB	Correct.
3	Correct	350 ms	15384 KB	Correct.
4	Correct	222 ms	5496 KB	Correct.
5	Correct	417 ms	11052 KB	Correct.
6	Correct	168 ms	8676 KB	Correct.
7	Correct	226 ms	4604 KB	Correct.
8	Correct	191 ms	2640 KB	Correct.
9	Correct	86 ms	1576 KB	Correct.
10	Correct	78 ms	1512 KB	Correct.
11	Correct	176 ms	2632 KB	Correct.
12	Correct	102 ms	1452 KB	Correct.
13	Correct	98 ms	1620 KB	Correct.
14	Correct	208 ms	8272 KB	Correct.
15	Correct	205 ms	3780 KB	Correct.
16	Correct	96 ms	1428 KB	Correct.
17	Correct	118 ms	1668 KB	Correct.
18	Correct	111 ms	1616 KB	Correct.
19	Correct	296 ms	2396 KB	Correct.
20	Correct	5 ms	604 KB	Correct.
21	Correct	9 ms	616 KB	Correct.
22	Correct	19 ms	1128 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	263 ms	1508 KB	Correct.
2	Correct	49 ms	824 KB	Correct.
3	Correct	252 ms	15492 KB	Correct.
4	Correct	279 ms	3260 KB	Correct.
5	Correct	1185 ms	11188 KB	Correct.
6	Correct	531 ms	8652 KB	Correct.
7	Correct	562 ms	7708 KB	Correct.
8	Correct	237 ms	2596 KB	Correct.
9	Correct	212 ms	1404 KB	Correct.
10	Correct	193 ms	1520 KB	Correct.
11	Correct	188 ms	1736 KB	Correct.
12	Correct	257 ms	1484 KB	Correct.
13	Correct	241 ms	1536 KB	Correct.
14	Correct	1183 ms	9240 KB	Correct.
15	Correct	1004 ms	8816 KB	Correct.
16	Correct	374 ms	4440 KB	Correct.
17	Correct	276 ms	2732 KB	Correct.
18	Correct	213 ms	1616 KB	Correct.
19	Correct	287 ms	1496 KB	Correct.
20	Correct	237 ms	1648 KB	Correct.
21	Correct	839 ms	2492 KB	Correct.
22	Correct	10 ms	608 KB	Correct.
23	Correct	15 ms	604 KB	Correct.
24	Correct	38 ms	1116 KB	Correct.

Submission #982090

Compilation message