oj.uz

답안 #968387

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
968387 2024-04-23T11:17:04 Z dubabuba 사이버랜드 (APIO23_cyberland) C++17
100 / 100
 1245 ms 76884 KB 
#include <bits/stdc++.h>
#include "cyberland.h"
 
#pragma GCC optimize("O3")
#pragma GCC target("lzcnt", "popcnt")
 
using namespace std;
 
typedef double dbl;
typedef vector<int> vi;
typedef long long i64;
typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair
 
template<typename T> void ono_min(T &MIN, T CMP) { if(MIN > CMP) MIN = CMP; }
template<typename T> void ono_max(T &MAX, T CMP) { if(MAX < CMP) MAX = CMP; }
 
const int mxk = 69;
const int mxn = 1e5 + 10;
vector<pii> adj[mxn];
 
dbl solve(int n, int m, int K, int h, vi x, vi y, vi c, vi arr) {
	for(int i = 0; i < n; i++)
		adj[i].clear();
	for(int i = 0; i < m; i++) {
		adj[x[i]].emplace_back(y[i], c[i]);
		adj[y[i]].emplace_back(x[i], c[i]);
	}
 
	bool in[n];
	memset(in, 0, sizeof in);
	priority_queue<pair<dbl, int>> pq[mxk];
	pq[0].push(MP(-0.0, 0));
	function<void(int)> dfs;
	dfs = [&](int u) -> void {
		if(in[u]) return;
		in[u] = 1;
		if(arr[u] == 0)
			pq[0].push(MP(-0.0, u));
		if(u == h) return;
		for(pii p : adj[u])
			if(!in[p.ff])
				dfs(p.ff);
	};
	dfs(0);
 
	dbl dis[mxk][n], ans = 1e18;
	for(int k = 0; k <= K && k < mxk; k++) {
		memset(in, 0, sizeof in);
		for(int i = 0; i < n; i++)
			dis[k][i] = 1e18;
		while(pq[k].size()) {
			dbl d = -pq[k].top().ff;
			int u = pq[k].top().ss;
			pq[k].pop();
 
			if(in[u]) continue;
			ono_min(dis[k][u], d);
			in[u] = 1;
			if(u == h) continue;
 
			for(pii p : adj[u]) {
				int v = p.ff;
				dbl w = p.ss;
				if(v * arr[v] == 0)
					continue;
				if(!in[v])
					pq[k].push(MP(-(dis[k][u] + w), v));
				if(arr[v] == 2 && k + 1 < mxk)
					pq[k + 1].push(MP(-(dis[k][u] + w) / 2.0, v));
			}
		}
		ono_min(ans, dis[k][h]);
	}
	return (ans < 1e18) ? ans : -1;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 2908 KB Correct.
2 Correct 17 ms 2904 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 3420 KB Correct.
2 Correct 21 ms 3420 KB Correct.
3 Correct 20 ms 3420 KB Correct.
4 Correct 25 ms 3420 KB Correct.
5 Correct 21 ms 3416 KB Correct.
6 Correct 20 ms 8796 KB Correct.
7 Correct 27 ms 8540 KB Correct.
8 Correct 16 ms 14680 KB Correct.
9 Correct 19 ms 2908 KB Correct.
10 Correct 19 ms 2908 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 3444 KB Correct.
2 Correct 23 ms 3420 KB Correct.
3 Correct 23 ms 3420 KB Correct.
4 Correct 21 ms 2904 KB Correct.
5 Correct 22 ms 2908 KB Correct.
6 Correct 8 ms 7772 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 41420 KB Correct.
2 Correct 72 ms 3680 KB Correct.
3 Correct 66 ms 3772 KB Correct.
4 Correct 64 ms 3704 KB Correct.
5 Correct 42 ms 2904 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 3420 KB Correct.
2 Correct 21 ms 3420 KB Correct.
3 Correct 20 ms 3420 KB Correct.
4 Correct 27 ms 8976 KB Correct.
5 Correct 17 ms 2908 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 3320 KB Correct.
2 Correct 19 ms 3416 KB Correct.
3 Correct 53 ms 48812 KB Correct.
4 Correct 16 ms 7260 KB Correct.
5 Correct 20 ms 2908 KB Correct.
6 Correct 20 ms 3420 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 124 ms 3932 KB Correct.
2 Correct 23 ms 4444 KB Correct.
3 Correct 328 ms 62052 KB Correct.
4 Correct 212 ms 16352 KB Correct.
5 Correct 472 ms 49552 KB Correct.
6 Correct 370 ms 38656 KB Correct.
7 Correct 216 ms 17468 KB Correct.
8 Correct 151 ms 4908 KB Correct.
9 Correct 112 ms 4024 KB Correct.
10 Correct 104 ms 3920 KB Correct.
11 Correct 132 ms 3596 KB Correct.
12 Correct 109 ms 3960 KB Correct.
13 Correct 120 ms 3868 KB Correct.
14 Correct 250 ms 31520 KB Correct.
15 Correct 195 ms 10528 KB Correct.
16 Correct 115 ms 3908 KB Correct.
17 Correct 126 ms 4012 KB Correct.
18 Correct 121 ms 4020 KB Correct.
19 Correct 253 ms 3828 KB Correct.
20 Correct 6 ms 2908 KB Correct.
21 Correct 9 ms 3544 KB Correct.
22 Correct 36 ms 6748 KB Correct.

Subtask #8
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 236 ms 4504 KB Correct.
2 Correct 44 ms 5208 KB Correct.
3 Correct 199 ms 63056 KB Correct.
4 Correct 233 ms 8900 KB Correct.
5 Correct 940 ms 76884 KB Correct.
6 Correct 829 ms 70788 KB Correct.
7 Correct 459 ms 27260 KB Correct.
8 Correct 168 ms 5908 KB Correct.
9 Correct 210 ms 5368 KB Correct.
10 Correct 213 ms 5400 KB Correct.
11 Correct 158 ms 3928 KB Correct.
12 Correct 216 ms 5608 KB Correct.
13 Correct 236 ms 5432 KB Correct.
14 Correct 1245 ms 49328 KB Correct.
15 Correct 672 ms 37140 KB Correct.
16 Correct 369 ms 16736 KB Correct.
17 Correct 203 ms 6944 KB Correct.
18 Correct 230 ms 5460 KB Correct.
19 Correct 234 ms 5472 KB Correct.
20 Correct 229 ms 5584 KB Correct.
21 Correct 495 ms 6280 KB Correct.
22 Correct 9 ms 2904 KB Correct.
23 Correct 15 ms 3944 KB Correct.
24 Correct 75 ms 10796 KB Correct.