oj.uz

답안 #914127

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
914127 2024-01-21T08:28:36 Z SmuggingSpun 사이버랜드 (APIO23_cyberland) C++17
100 / 100
 862 ms 10824 KB 
#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

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

Subtask #2
8.0 / 8.0

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

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

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

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

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

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

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