oj.uz

답안 #982090

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
982090 2024-05-13T19:19:28 Z vjudge1 사이버랜드 (APIO23_cyberland) C++17
100 / 100
 1185 ms 15492 KB 
// 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

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 604 KB Correct.
2 Correct 21 ms 856 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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.