oj.uz

답안 #756864

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
756864 2023-06-12T10:40:54 Z DarkMatter 사이버랜드 (APIO23_cyberland) C++17
78 / 100
 1189 ms 24048 KB 
#include "cyberland.h"

/* 	* In the name of GOD  */

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef long double ld;
#define F first
#define S second
#define mk make_pair
const ll N = 2e5 + 10, INF = 2e18 + 10;
vector <pair <int, ll>> g[N];
ld dis[N], od[N], x[N];
int n, h;
bool vis[N];
vector <int> ww;

void dijkstra() {
	priority_queue <pair <ld, int>> q;
	for (int s = 0; s < n; s++)
		q.push(make_pair((ld)-1.0 * dis[s], s));
	while (!q.empty()) {
		pair <ld, int> p = (q.top());
		int x = p.S;
		q.pop();
		if (dis[x] != -1 * p.F || x == h)
			continue;
		ld d = dis[x];
		for (auto [y, w] : g[x]) {
			if (dis[y] <= d + w) {
				continue;
			}
			dis[y] = d + w;
			q.push(make_pair(-1 * dis[y], y));
		}
	}
}

void dfs(int v) {
	vis[v] = true;
	for (auto [u, w] : g[v]) {
		if (!vis[u])
			dfs(u);
	}
}

void dfs2(int v) {
	vis[v] = true;
	ww.push_back(v);
	for (auto [u, w] : g[v]) {
		if (!vis[u] && u != h)
			dfs2(u);
	}
}

double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
	K = min(K, 70);
	n = N;
	h = H;
	for (int i = 0; i <= n; i++)
		g[i].clear(), vis[i] = false;
	for (int i = 0; i < M; i++) {
		g[x[i]].push_back(mk(y[i], c[i]));
		g[y[i]].push_back(mk(x[i], c[i]));
	}
	dfs(0);
	if (!vis[H]) {
		for (int i = 0; i <= n; i++)
			g[i].clear(), vis[i] = false;
		return -1;
	}
	for (int i = 0; i < n; i++) {
		dis[i] = INF;
	}
	for (int i = 0; i <= n; i++)
		vis[i] = false;
	ww.clear();
	dfs2(0);
	for (int i : ww) {
		if (i == 0 || arr[i] == 0)
			dis[i] = 0;
	}
	ld mn = INF;
	for (int i = 0; i <= K; i++) {
		dijkstra();
		mn = min(mn, dis[H]);
		dis[H] = INF;
		for (int i = 0; i < n; i++)
			od[i] = dis[i];
		for (int i = 0; i < n; i++) {
			if (arr[i] == 2) {
				ld mnn = INF;
				for (auto [j, w] : g[i]) {
					mnn = min(mnn, od[j] + w);
				}
				dis[i] = min(dis[i], (mnn) / (ld)2);
			}
		}
	}
	for (int i = 0; i <= n; i++)
		g[i].clear(), vis[i] = false;
	return mn;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 5136 KB Correct.
2 Correct 68 ms 5072 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 236 ms 5344 KB Correct.
2 Correct 262 ms 5364 KB Correct.
3 Correct 253 ms 5372 KB Correct.
4 Correct 282 ms 5404 KB Correct.
5 Correct 265 ms 5448 KB Correct.
6 Correct 364 ms 7148 KB Correct.
7 Correct 439 ms 7124 KB Correct.
8 Correct 201 ms 8988 KB Correct.
9 Correct 182 ms 5100 KB Correct.
10 Correct 169 ms 5208 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 265 ms 5272 KB Correct.
2 Correct 258 ms 5272 KB Correct.
3 Correct 234 ms 5384 KB Correct.
4 Correct 217 ms 5092 KB Correct.
5 Correct 191 ms 5076 KB Correct.
6 Correct 76 ms 6484 KB Correct.

Subtask #4
0.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1040 ms 16436 KB Correct.
2 Incorrect 377 ms 5292 KB Wrong Answer.
3 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 5396 KB Correct.
2 Correct 136 ms 5376 KB Correct.
3 Correct 146 ms 5412 KB Correct.
4 Correct 210 ms 7200 KB Correct.
5 Correct 82 ms 5092 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 149 ms 5344 KB Correct.
2 Correct 94 ms 5324 KB Correct.
3 Correct 48 ms 11484 KB Correct.
4 Correct 103 ms 6828 KB Correct.
5 Correct 95 ms 5196 KB Correct.
6 Correct 129 ms 5400 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 153 ms 5376 KB Correct.
2 Correct 21 ms 5396 KB Correct.
3 Correct 1189 ms 24048 KB Correct.
4 Correct 799 ms 9788 KB Correct.
5 Correct 601 ms 16848 KB Correct.
6 Correct 177 ms 12484 KB Correct.
7 Correct 724 ms 9828 KB Correct.
8 Correct 474 ms 6020 KB Correct.
9 Correct 121 ms 5348 KB Correct.
10 Correct 133 ms 5444 KB Correct.
11 Correct 427 ms 5472 KB Correct.
12 Correct 154 ms 5404 KB Correct.
13 Correct 132 ms 5416 KB Correct.
14 Correct 542 ms 14928 KB Correct.
15 Correct 531 ms 7752 KB Correct.
16 Correct 123 ms 5432 KB Correct.
17 Correct 172 ms 5524 KB Correct.
18 Correct 143 ms 5388 KB Correct.
19 Correct 426 ms 5380 KB Correct.
20 Correct 11 ms 5076 KB Correct.
21 Correct 12 ms 5204 KB Correct.
22 Correct 14 ms 5876 KB Correct.

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 299 ms 5368 KB Wrong Answer.
2 Halted 0 ms 0 KB -