oj.uz

Submission #749256

# Submission time Handle Problem Language Result Execution time Memory
749256 2023-05-27T15:15:48 Z SanguineChameleon Cyberland (APIO23_cyberland) C++17
100 / 100
 2023 ms 102968 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, 100);
	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 24 ms 2772 KB Correct.
2 Correct 27 ms 2780 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3688 KB Correct.
2 Correct 30 ms 3644 KB Correct.
3 Correct 29 ms 3692 KB Correct.
4 Correct 34 ms 3716 KB Correct.
5 Correct 33 ms 3668 KB Correct.
6 Correct 31 ms 12532 KB Correct.
7 Correct 40 ms 12432 KB Correct.
8 Correct 24 ms 22484 KB Correct.
9 Correct 28 ms 2772 KB Correct.
10 Correct 27 ms 2812 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 3720 KB Correct.
2 Correct 32 ms 3668 KB Correct.
3 Correct 36 ms 3780 KB Correct.
4 Correct 39 ms 2772 KB Correct.
5 Correct 31 ms 2828 KB Correct.
6 Correct 10 ms 10964 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 61328 KB Correct.
2 Correct 110 ms 3668 KB Correct.
3 Correct 94 ms 3648 KB Correct.
4 Correct 99 ms 3660 KB Correct.
5 Correct 75 ms 2772 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3796 KB Correct.
2 Correct 29 ms 3668 KB Correct.
3 Correct 28 ms 3760 KB Correct.
4 Correct 34 ms 12500 KB Correct.
5 Correct 24 ms 2816 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3760 KB Correct.
2 Correct 26 ms 3796 KB Correct.
3 Correct 96 ms 78932 KB Correct.
4 Correct 24 ms 9812 KB Correct.
5 Correct 30 ms 2772 KB Correct.
6 Correct 34 ms 3732 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 3788 KB Correct.
2 Correct 23 ms 4432 KB Correct.
3 Correct 697 ms 98640 KB Correct.
4 Correct 301 ms 24400 KB Correct.
5 Correct 567 ms 41688 KB Correct.
6 Correct 228 ms 16708 KB Correct.
7 Correct 327 ms 26648 KB Correct.
8 Correct 206 ms 6268 KB Correct.
9 Correct 100 ms 3816 KB Correct.
10 Correct 100 ms 3736 KB Correct.
11 Correct 186 ms 3980 KB Correct.
12 Correct 123 ms 3788 KB Correct.
13 Correct 105 ms 3896 KB Correct.
14 Correct 318 ms 49364 KB Correct.
15 Correct 235 ms 15436 KB Correct.
16 Correct 110 ms 3764 KB Correct.
17 Correct 131 ms 3888 KB Correct.
18 Correct 133 ms 3748 KB Correct.
19 Correct 317 ms 3816 KB Correct.
20 Correct 7 ms 2772 KB Correct.
21 Correct 11 ms 3576 KB Correct.
22 Correct 17 ms 3912 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 3788 KB Correct.
2 Correct 47 ms 4464 KB Correct.
3 Correct 586 ms 102968 KB Correct.
4 Correct 344 ms 9036 KB Correct.
5 Correct 1754 ms 41848 KB Correct.
6 Correct 501 ms 16680 KB Correct.
7 Correct 697 ms 38772 KB Correct.
8 Correct 281 ms 4252 KB Correct.
9 Correct 252 ms 3796 KB Correct.
10 Correct 240 ms 3760 KB Correct.
11 Correct 212 ms 2852 KB Correct.
12 Correct 265 ms 3860 KB Correct.
13 Correct 263 ms 3788 KB Correct.
14 Correct 2023 ms 42924 KB Correct.
15 Correct 1689 ms 52488 KB Correct.
16 Correct 493 ms 20496 KB Correct.
17 Correct 323 ms 6260 KB Correct.
18 Correct 269 ms 3760 KB Correct.
19 Correct 308 ms 3876 KB Correct.
20 Correct 307 ms 3788 KB Correct.
21 Correct 961 ms 3840 KB Correct.
22 Correct 14 ms 2804 KB Correct.
23 Correct 21 ms 3540 KB Correct.
24 Correct 30 ms 3916 KB Correct.