oj.uz

Submission #749258

# Submission time Handle Problem Language Result Execution time Memory
749258 2023-05-27T15:16:42 Z SanguineChameleon Cyberland (APIO23_cyberland) C++17
100 / 100
 1401 ms 102964 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 24 ms 2764 KB Correct.
2 Correct 24 ms 2816 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3732 KB Correct.
2 Correct 32 ms 3748 KB Correct.
3 Correct 39 ms 3736 KB Correct.
4 Correct 38 ms 3724 KB Correct.
5 Correct 31 ms 3728 KB Correct.
6 Correct 36 ms 12500 KB Correct.
7 Correct 40 ms 12400 KB Correct.
8 Correct 27 ms 22516 KB Correct.
9 Correct 29 ms 2820 KB Correct.
10 Correct 29 ms 2808 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3644 KB Correct.
2 Correct 42 ms 3664 KB Correct.
3 Correct 30 ms 3764 KB Correct.
4 Correct 31 ms 2772 KB Correct.
5 Correct 35 ms 2808 KB Correct.
6 Correct 12 ms 10884 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 61320 KB Correct.
2 Correct 119 ms 3724 KB Correct.
3 Correct 101 ms 3748 KB Correct.
4 Correct 114 ms 3712 KB Correct.
5 Correct 73 ms 2804 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3796 KB Correct.
2 Correct 33 ms 3772 KB Correct.
3 Correct 34 ms 3688 KB Correct.
4 Correct 38 ms 12500 KB Correct.
5 Correct 29 ms 2800 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3788 KB Correct.
2 Correct 26 ms 3784 KB Correct.
3 Correct 106 ms 78948 KB Correct.
4 Correct 25 ms 9812 KB Correct.
5 Correct 38 ms 2816 KB Correct.
6 Correct 28 ms 3796 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 3904 KB Correct.
2 Correct 19 ms 4436 KB Correct.
3 Correct 637 ms 98616 KB Correct.
4 Correct 325 ms 24400 KB Correct.
5 Correct 577 ms 41768 KB Correct.
6 Correct 179 ms 16724 KB Correct.
7 Correct 303 ms 26652 KB Correct.
8 Correct 213 ms 6280 KB Correct.
9 Correct 104 ms 3916 KB Correct.
10 Correct 101 ms 3792 KB Correct.
11 Correct 191 ms 4092 KB Correct.
12 Correct 114 ms 3820 KB Correct.
13 Correct 109 ms 3804 KB Correct.
14 Correct 371 ms 49496 KB Correct.
15 Correct 250 ms 15228 KB Correct.
16 Correct 107 ms 3772 KB Correct.
17 Correct 132 ms 3800 KB Correct.
18 Correct 153 ms 3784 KB Correct.
19 Correct 343 ms 3744 KB Correct.
20 Correct 8 ms 2772 KB Correct.
21 Correct 10 ms 3540 KB Correct.
22 Correct 15 ms 3924 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 3676 KB Correct.
2 Correct 33 ms 4556 KB Correct.
3 Correct 469 ms 102964 KB Correct.
4 Correct 282 ms 9160 KB Correct.
5 Correct 1207 ms 41684 KB Correct.
6 Correct 356 ms 16688 KB Correct.
7 Correct 517 ms 38780 KB Correct.
8 Correct 236 ms 4256 KB Correct.
9 Correct 179 ms 3816 KB Correct.
10 Correct 176 ms 3788 KB Correct.
11 Correct 172 ms 2828 KB Correct.
12 Correct 195 ms 3704 KB Correct.
13 Correct 189 ms 3820 KB Correct.
14 Correct 1401 ms 42984 KB Correct.
15 Correct 1129 ms 52492 KB Correct.
16 Correct 460 ms 20736 KB Correct.
17 Correct 268 ms 6360 KB Correct.
18 Correct 183 ms 3740 KB Correct.
19 Correct 235 ms 3700 KB Correct.
20 Correct 214 ms 3728 KB Correct.
21 Correct 628 ms 3668 KB Correct.
22 Correct 11 ms 2772 KB Correct.
23 Correct 16 ms 3576 KB Correct.
24 Correct 22 ms 3924 KB Correct.