oj.uz

답안 #1071959

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1071959 2024-08-23T12:45:10 Z Halym2007 사이버랜드 (APIO23_cyberland) C++17
100 / 100
 1581 ms 85328 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <double, int>
const int N = 2e5 + 5;
const int git = 70;
vector <pair <int, int>> v[N];
double dis[git][N];
set <pii> q[N];
int n, m, k, h;
double jogap = 1e16;
bool vis[N];
 
void dfs (ll x) {
	vis[x] = 1;
	for (auto i : v[x]) {
		if (vis[i.ff]) continue;
		dfs(i.ff);
	}
}
 
 
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> a) {
	n = N;m = M;k = K;h = H;
	for (int i = 0; i < m; ++i) {
		v[x[i]].pb ({y[i], c[i]});
		v[y[i]].pb ({x[i], c[i]});
	}
	jogap = 1e16;
	vis[h] = 1;
	if (k >= git - 1) k = git - 2;
	dfs (0);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < git; ++j) {
			dis[j][i] = 1e16;
		}
	}
	q[0].insert ({0, 0});
	dis[0][0] = 0;
	for (int i = 0; i < n; ++i) {
		if (!a[i] and vis[i]) {
			q[0].insert ({0, i});
			dis[0][i] = 0;
		}
	}
	for (int i = 0; i <= k; ++i) {
		while (!q[i].empty()) {
			int x = (*q[i].begin()).ss;
			q[i].erase(q[i].begin());
			if (x == h) continue;
			for (auto j : v[x]) {
				double val = dis[i][x] + j.ss;
				if (val < dis[i][j.ff]) {
					dis[i][j.ff] = val;
					q[i].insert ({val, j.ff});
				}
				if (a[j.ff] == 2) {
					val /= 2;
					if (dis[i + 1][j.ff] > val) {
						dis[i + 1][j.ff] =  val;
						q[i + 1].insert ({val, j.ff});
					}
				}
			} 
		}
		jogap = min (jogap, dis[i][h]);
	}
	
	if (jogap == (double)1e16) jogap = -1;
	for (int i = 0; i < n; ++i) {
		v[i].clear();
		vis[i] = 0;
	}
	for (int i = 0; i < git; ++i) {
		q[i].clear();
	}
	return jogap;
}
 
 
//int main() {
//	freopen ("input.txt", "r", stdin);
//  int T;
//  assert(1 == scanf("%d", &T));
//  while (T--){
//    int N,M,K,H;
//    assert(4 == scanf("%d %d %d\n%d", &N, &M, &K, &H));
//    std::vector<int> x(M);
//    std::vector<int> y(M);
//    std::vector<int> c(M);
//    std::vector<int> arr(N);
//    for (int i=0;i<N;i++)
//      assert(1 == scanf("%d", &arr[i]));
//    for (int i=0;i<M;i++)
//      assert(3 == scanf("%d %d %d", &x[i], &y[i], &c[i]));
//    printf("%.12lf\n", solve(N, M, K, H, x, y, c, arr));
//  }
//}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 30300 KB Correct.
2 Correct 19 ms 24152 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 24668 KB Correct.
2 Correct 23 ms 24668 KB Correct.
3 Correct 29 ms 32856 KB Correct.
4 Correct 26 ms 32604 KB Correct.
5 Correct 28 ms 26716 KB Correct.
6 Correct 27 ms 37464 KB Correct.
7 Correct 43 ms 35420 KB Correct.
8 Correct 30 ms 40796 KB Correct.
9 Correct 24 ms 32088 KB Correct.
10 Correct 22 ms 24152 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 24668 KB Correct.
2 Correct 27 ms 32600 KB Correct.
3 Correct 25 ms 30812 KB Correct.
4 Correct 25 ms 30296 KB Correct.
5 Correct 32 ms 24088 KB Correct.
6 Correct 15 ms 28764 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 150 ms 57428 KB Correct.
2 Correct 128 ms 24552 KB Correct.
3 Correct 85 ms 30800 KB Correct.
4 Correct 136 ms 32744 KB Correct.
5 Correct 65 ms 30044 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 32840 KB Correct.
2 Correct 25 ms 30808 KB Correct.
3 Correct 30 ms 24668 KB Correct.
4 Correct 38 ms 31580 KB Correct.
5 Correct 34 ms 30040 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 30808 KB Correct.
2 Correct 24 ms 30812 KB Correct.
3 Correct 49 ms 70748 KB Correct.
4 Correct 17 ms 34140 KB Correct.
5 Correct 22 ms 32092 KB Correct.
6 Correct 20 ms 26712 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 129 ms 24584 KB Correct.
2 Correct 31 ms 31068 KB Correct.
3 Correct 479 ms 81860 KB Correct.
4 Correct 361 ms 43600 KB Correct.
5 Correct 721 ms 54356 KB Correct.
6 Correct 385 ms 40572 KB Correct.
7 Correct 311 ms 42840 KB Correct.
8 Correct 252 ms 32036 KB Correct.
9 Correct 94 ms 30792 KB Correct.
10 Correct 119 ms 32808 KB Correct.
11 Correct 199 ms 30916 KB Correct.
12 Correct 103 ms 24656 KB Correct.
13 Correct 126 ms 24664 KB Correct.
14 Correct 327 ms 50768 KB Correct.
15 Correct 277 ms 36944 KB Correct.
16 Correct 105 ms 30804 KB Correct.
17 Correct 128 ms 26740 KB Correct.
18 Correct 129 ms 26716 KB Correct.
19 Correct 316 ms 30784 KB Correct.
20 Correct 15 ms 30040 KB Correct.
21 Correct 17 ms 30732 KB Correct.
22 Correct 26 ms 24924 KB Correct.

Subtask #8
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 190 ms 32708 KB Correct.
2 Correct 42 ms 31188 KB Correct.
3 Correct 326 ms 85328 KB Correct.
4 Correct 311 ms 35664 KB Correct.
5 Correct 1581 ms 54596 KB Correct.
6 Correct 822 ms 40528 KB Correct.
7 Correct 564 ms 51536 KB Correct.
8 Correct 234 ms 31144 KB Correct.
9 Correct 153 ms 32844 KB Correct.
10 Correct 159 ms 30812 KB Correct.
11 Correct 139 ms 32372 KB Correct.
12 Correct 170 ms 24656 KB Correct.
13 Correct 168 ms 30816 KB Correct.
14 Correct 1420 ms 49736 KB Correct.
15 Correct 968 ms 52228 KB Correct.
16 Correct 486 ms 36176 KB Correct.
17 Correct 258 ms 32080 KB Correct.
18 Correct 170 ms 32832 KB Correct.
19 Correct 187 ms 26704 KB Correct.
20 Correct 177 ms 30804 KB Correct.
21 Correct 518 ms 30792 KB Correct.
22 Correct 14 ms 25948 KB Correct.
23 Correct 14 ms 24608 KB Correct.
24 Correct 51 ms 24924 KB Correct.