oj.uz

Submission #983316

# Submission time Handle Problem Language Result Execution time Memory
983316 2024-05-15T10:10:44 Z feev1x Cyberland (APIO23_cyberland) C++17
97 / 100
 2279 ms 2097152 KB 
#include "cyberland.h"

#include <bits/stdc++.h>
using namespace std;

const double INF = numeric_limits<double>::max();

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) {
    vector<vector<pair<int, double>>> g(N);
    for (int i = 0; i < M; ++i) {
		g[x[i]].emplace_back(y[i], c[i]);
		g[y[i]].emplace_back(x[i], c[i]);
	}
	vector<vector<double>> dis(N, vector<double>(K + 1, INF));
	dis[0][0] = 0;
	set<tuple<double, int, int>> q;
	q.emplace(dis[0][0], 0, 0);
	while (!q.empty()) {
		auto [w, nearest, i] = *q.begin();
		q.erase(q.begin());
		if(nearest == H) continue;
		for (auto [to, weight]: g[nearest]) {
			if (arr[to] == 0) weight = -dis[nearest][i];
			if (dis[to][i] > dis[nearest][i] + weight) {
				q.erase(tuple{dis[to][i], to, i});
				dis[to][i] = dis[nearest][i] + weight;
				q.emplace(dis[to][i], to, i);
			}
			if (arr[to] == 2 && i < K && dis[to][i + 1] > (dis[nearest][i] + weight) / 2.) {
				q.erase(tuple{dis[to][i + 1], to, i + 1});
				dis[to][i + 1] = (dis[nearest][i] + weight) / 2.;
				q.emplace(dis[to][i + 1], to, i + 1);
			}
		}
	}
	double res = INF;
	for (int i = 0; i <= K; ++i) res = min(dis[H][i], res);
	if (res == INF) res = -1;
	return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 856 KB Correct.
2 Correct 20 ms 860 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1628 KB Correct.
2 Correct 29 ms 1876 KB Correct.
3 Correct 27 ms 1884 KB Correct.
4 Correct 31 ms 1724 KB Correct.
5 Correct 28 ms 1712 KB Correct.
6 Correct 27 ms 4992 KB Correct.
7 Correct 34 ms 5296 KB Correct.
8 Correct 23 ms 8476 KB Correct.
9 Correct 30 ms 1444 KB Correct.
10 Correct 28 ms 1360 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1712 KB Correct.
2 Correct 29 ms 1732 KB Correct.
3 Correct 29 ms 1612 KB Correct.
4 Correct 30 ms 1360 KB Correct.
5 Correct 31 ms 1484 KB Correct.
6 Correct 7 ms 3684 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 23728 KB Correct.
2 Correct 588 ms 1972 KB Correct.
3 Correct 510 ms 1748 KB Correct.
4 Correct 503 ms 1908 KB Correct.
5 Correct 333 ms 1404 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1696 KB Correct.
2 Correct 26 ms 1876 KB Correct.
3 Correct 27 ms 1868 KB Correct.
4 Correct 28 ms 4956 KB Correct.
5 Correct 22 ms 1368 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1600 KB Correct.
2 Correct 26 ms 1720 KB Correct.
3 Correct 46 ms 31164 KB Correct.
4 Correct 18 ms 3228 KB Correct.
5 Correct 32 ms 1292 KB Correct.
6 Correct 25 ms 1740 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 2180 KB Correct.
2 Correct 34 ms 1748 KB Correct.
3 Correct 2279 ms 31576 KB Correct.
4 Correct 1648 ms 9564 KB Correct.
5 Correct 1249 ms 48884 KB Correct.
6 Correct 480 ms 23444 KB Correct.
7 Correct 1550 ms 9520 KB Correct.
8 Correct 1383 ms 3824 KB Correct.
9 Correct 260 ms 2084 KB Correct.
10 Correct 273 ms 1932 KB Correct.
11 Correct 1259 ms 2628 KB Correct.
12 Correct 322 ms 2032 KB Correct.
13 Correct 263 ms 2028 KB Correct.
14 Correct 1456 ms 11408 KB Correct.
15 Correct 1854 ms 4796 KB Correct.
16 Correct 277 ms 2376 KB Correct.
17 Correct 332 ms 2064 KB Correct.
18 Correct 349 ms 2136 KB Correct.
19 Correct 1027 ms 3044 KB Correct.
20 Correct 21 ms 604 KB Correct.
21 Correct 25 ms 784 KB Correct.
22 Correct 31 ms 2440 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 1184 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -