oj.uz

Submission #1002080

# Submission time Handle Problem Language Result Execution time Memory
1002080 2024-06-19T09:45:05 Z underwaterkillerwhale Cyberland (APIO23_cyberland) C++17
100 / 100
 987 ms 105472 KB 
#include <bits/stdc++.h>
#include "cyberland.h"
using namespace std;
 
const int maxN = 1e5 + 20;
const int maxK = 1e2 + 20;
const double inf = 1e18;
bool flag[maxN];
double dist[maxN][maxK];
vector<pair<int, int>> adj[maxN];
 
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
	K = min(K, 67);
	for (int i = 0; i < N; i++) {
		flag[i] = false;
		for (int j = 0; j <= K; j++) {
			dist[i][j] = inf;
		}
		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]);
	}
	flag[0] = true;
	deque<int> q;
	q.push_back(0);
	while (!q.empty()) {
		int u = q.front();
		q.pop_front();
		for (auto e: adj[u]) {
			int v = e.first;
			if (v != H && !flag[v]) {
				flag[v] = true;
				q.push_back(v);
			}
		}
	}
	for (int i = 0; i < N; i++) {
		if (flag[i] && (i == 0 || arr[i] == 0)) {
			dist[i][0] = 0.0;
		}
	}
	double res = inf;
	for (int k = 0; k <= K; k++) {
		priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> q;
		for (int i = 0; i < N; i++) {
			if (i != H && dist[i][k] != inf) {
				q.emplace(dist[i][k], i);
			} 
		}
		while (!q.empty()) {
			int u = q.top().second;
			double cur_d = q.top().first;
			q.pop();
			if (cur_d != dist[u][k]) {
				continue;
			}
			for (auto e: adj[u]) {
				int v = e.first;
				int w = e.second;
				if (dist[u][k] + w < dist[v][k]) {
					dist[v][k] = dist[u][k] + w;
					if (v != H) {
						q.emplace(dist[v][k], v);
					}
				}
				if (arr[u] == 2) {
					dist[v][k + 1] = min(dist[v][k + 1], dist[u][k] / 2.0 + w);
				}
			}
		}
		res = min(res, dist[H][k]);
	}
	if (res == inf) {
		return -1;
	}
	else {
		return res;
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3160 KB Correct.
2 Correct 15 ms 3164 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 4440 KB Correct.
2 Correct 20 ms 4444 KB Correct.
3 Correct 19 ms 4564 KB Correct.
4 Correct 27 ms 4444 KB Correct.
5 Correct 21 ms 4432 KB Correct.
6 Correct 22 ms 13404 KB Correct.
7 Correct 29 ms 13148 KB Correct.
8 Correct 18 ms 22876 KB Correct.
9 Correct 18 ms 3672 KB Correct.
10 Correct 18 ms 3728 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4440 KB Correct.
2 Correct 22 ms 4584 KB Correct.
3 Correct 20 ms 4700 KB Correct.
4 Correct 20 ms 3512 KB Correct.
5 Correct 20 ms 3612 KB Correct.
6 Correct 8 ms 11168 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 62480 KB Correct.
2 Correct 72 ms 4476 KB Correct.
3 Correct 61 ms 4432 KB Correct.
4 Correct 66 ms 4460 KB Correct.
5 Correct 41 ms 3668 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 4700 KB Correct.
2 Correct 19 ms 4496 KB Correct.
3 Correct 19 ms 4568 KB Correct.
4 Correct 23 ms 13392 KB Correct.
5 Correct 19 ms 3664 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 4484 KB Correct.
2 Correct 17 ms 4700 KB Correct.
3 Correct 63 ms 80128 KB Correct.
4 Correct 16 ms 10332 KB Correct.
5 Correct 18 ms 3616 KB Correct.
6 Correct 19 ms 4696 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 4520 KB Correct.
2 Correct 13 ms 4696 KB Correct.
3 Correct 352 ms 100292 KB Correct.
4 Correct 215 ms 25868 KB Correct.
5 Correct 376 ms 43076 KB Correct.
6 Correct 135 ms 17852 KB Correct.
7 Correct 222 ms 27900 KB Correct.
8 Correct 142 ms 7508 KB Correct.
9 Correct 64 ms 4692 KB Correct.
10 Correct 60 ms 4472 KB Correct.
11 Correct 124 ms 5460 KB Correct.
12 Correct 74 ms 4640 KB Correct.
13 Correct 68 ms 4688 KB Correct.
14 Correct 232 ms 50512 KB Correct.
15 Correct 186 ms 16488 KB Correct.
16 Correct 68 ms 4688 KB Correct.
17 Correct 80 ms 4676 KB Correct.
18 Correct 94 ms 4688 KB Correct.
19 Correct 243 ms 5348 KB Correct.
20 Correct 5 ms 2908 KB Correct.
21 Correct 6 ms 3676 KB Correct.
22 Correct 9 ms 4188 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 4760 KB Correct.
2 Correct 21 ms 4700 KB Correct.
3 Correct 153 ms 105472 KB Correct.
4 Correct 236 ms 11340 KB Correct.
5 Correct 741 ms 43624 KB Correct.
6 Correct 268 ms 18348 KB Correct.
7 Correct 434 ms 41152 KB Correct.
8 Correct 183 ms 6228 KB Correct.
9 Correct 97 ms 4692 KB Correct.
10 Correct 101 ms 4692 KB Correct.
11 Correct 104 ms 3976 KB Correct.
12 Correct 107 ms 4772 KB Correct.
13 Correct 106 ms 4692 KB Correct.
14 Correct 987 ms 44740 KB Correct.
15 Correct 677 ms 54656 KB Correct.
16 Correct 368 ms 22816 KB Correct.
17 Correct 182 ms 8320 KB Correct.
18 Correct 96 ms 4948 KB Correct.
19 Correct 130 ms 4944 KB Correct.
20 Correct 111 ms 4784 KB Correct.
21 Correct 388 ms 5716 KB Correct.
22 Correct 7 ms 2908 KB Correct.
23 Correct 11 ms 3712 KB Correct.
24 Correct 16 ms 4184 KB Correct.