oj.uz

Submission #977534

# Submission time Handle Problem Language Result Execution time Memory
977534 2024-05-08T06:24:17 Z yusuf12360 Cyberland (APIO23_cyberland) C++17
100 / 100
 1188 ms 15264 KB 
#include<bits/stdc++.h>
using namespace std;
const double INF=1e18;
double 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, double>>> adj(n);
	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]});
	}
	vector<double> dist(n), temp(n); 
	for(auto &p : dist) p=INF;
	for(auto &p : temp) p=INF;
	priority_queue<pair<double, int>> pq;
	double ans=INF; temp[0]=0.;
	for(int j=0; j<=k; j++) {
		vector<double> temp(n); for(double &p : temp) p=INF;
		if(j) {
			for(int i=0; i<n; i++) {
				if(a[i]==1 || dist[i]==INF) continue;
				if(a[i]==0) temp[i]=0;
				pq.push({-dist[i]/2., i});
			}
		} else pq.push({0., 0});
		while(!pq.empty()) {
			auto [cur, u]=pq.top(); cur=-cur;
			pq.pop();
			if(u==h) continue;
			for(auto [v, w] : adj[u]) {
				if(temp[v]>cur+w) {
					if(a[v]==0) temp[v]=0.;
					else temp[v]=cur+w;
					pq.push({-temp[v], v});
				}
			}
		}
		ans=min(ans, temp[h]);
		if(j==0 && temp[h]==INF) break;
		swap(temp, dist);
	}
	return (ans<INF ? ans : -1.);
}
/*int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, m, k, h; cin >> n >> m >> k >> h;
	vector<int> x(m), y(m), c(m), a(n);
	for(int &p : x) cin >> p;
	for(int &p : y) cin >> p;
	for(int &p : c) cin >> p;
	for(int &p : a) cin >> p;
	cout << solve(n, m, k, h, x, y, c, a) << '\n';
	return 0;
}*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 860 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 1368 KB Correct.
2 Correct 24 ms 1616 KB Correct.
3 Correct 24 ms 1616 KB Correct.
4 Correct 24 ms 1628 KB Correct.
5 Correct 25 ms 1472 KB Correct.
6 Correct 20 ms 2616 KB Correct.
7 Correct 26 ms 2720 KB Correct.
8 Correct 11 ms 3516 KB Correct.
9 Correct 23 ms 1372 KB Correct.
10 Correct 24 ms 1372 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 1848 KB Correct.
2 Correct 129 ms 1596 KB Correct.
3 Correct 114 ms 1496 KB Correct.
4 Correct 70 ms 1360 KB Correct.
5 Correct 70 ms 1360 KB Correct.
6 Correct 37 ms 1624 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 9396 KB Correct.
2 Correct 116 ms 1628 KB Correct.
3 Correct 94 ms 1620 KB Correct.
4 Correct 109 ms 1580 KB Correct.
5 Correct 57 ms 1408 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1708 KB Correct.
2 Correct 22 ms 1624 KB Correct.
3 Correct 22 ms 1616 KB Correct.
4 Correct 22 ms 2500 KB Correct.
5 Correct 19 ms 1112 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 1364 KB Correct.
2 Correct 48 ms 1368 KB Correct.
3 Correct 33 ms 12116 KB Correct.
4 Correct 63 ms 2140 KB Correct.
5 Correct 42 ms 1360 KB Correct.
6 Correct 59 ms 1372 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 1468 KB Correct.
2 Correct 18 ms 604 KB Correct.
3 Correct 316 ms 15236 KB Correct.
4 Correct 223 ms 5056 KB Correct.
5 Correct 393 ms 10904 KB Correct.
6 Correct 168 ms 8656 KB Correct.
7 Correct 226 ms 4560 KB Correct.
8 Correct 190 ms 2728 KB Correct.
9 Correct 87 ms 1364 KB Correct.
10 Correct 80 ms 1564 KB Correct.
11 Correct 163 ms 2548 KB Correct.
12 Correct 106 ms 1864 KB Correct.
13 Correct 99 ms 1644 KB Correct.
14 Correct 224 ms 8084 KB Correct.
15 Correct 206 ms 3572 KB Correct.
16 Correct 89 ms 1436 KB Correct.
17 Correct 115 ms 1872 KB Correct.
18 Correct 98 ms 1600 KB Correct.
19 Correct 300 ms 2336 KB Correct.
20 Correct 5 ms 608 KB Correct.
21 Correct 7 ms 604 KB Correct.
22 Correct 14 ms 1116 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 1544 KB Correct.
2 Correct 49 ms 604 KB Correct.
3 Correct 249 ms 15264 KB Correct.
4 Correct 286 ms 3312 KB Correct.
5 Correct 1188 ms 10816 KB Correct.
6 Correct 503 ms 8664 KB Correct.
7 Correct 527 ms 7380 KB Correct.
8 Correct 237 ms 2780 KB Correct.
9 Correct 211 ms 1452 KB Correct.
10 Correct 184 ms 1364 KB Correct.
11 Correct 167 ms 2108 KB Correct.
12 Correct 259 ms 1568 KB Correct.
13 Correct 239 ms 1620 KB Correct.
14 Correct 1158 ms 9052 KB Correct.
15 Correct 947 ms 8804 KB Correct.
16 Correct 374 ms 4212 KB Correct.
17 Correct 295 ms 2540 KB Correct.
18 Correct 208 ms 1428 KB Correct.
19 Correct 294 ms 1592 KB Correct.
20 Correct 239 ms 1488 KB Correct.
21 Correct 846 ms 2368 KB Correct.
22 Correct 10 ms 604 KB Correct.
23 Correct 15 ms 604 KB Correct.
24 Correct 39 ms 1332 KB Correct.