oj.uz

Submission #983319

# Submission time Handle Problem Language Result Execution time Memory
983319 2024-05-15T10:11:10 Z vjudge1 Cyberland (APIO23_cyberland) C++17
97 / 100
 2231 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 32 ms 528 KB Correct.
2 Correct 30 ms 592 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 856 KB Correct.
2 Correct 28 ms 848 KB Correct.
3 Correct 27 ms 824 KB Correct.
4 Correct 30 ms 864 KB Correct.
5 Correct 32 ms 884 KB Correct.
6 Correct 28 ms 4256 KB Correct.
7 Correct 47 ms 3932 KB Correct.
8 Correct 24 ms 8028 KB Correct.
9 Correct 28 ms 568 KB Correct.
10 Correct 32 ms 536 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 600 KB Correct.
2 Correct 28 ms 860 KB Correct.
3 Correct 27 ms 856 KB Correct.
4 Correct 33 ms 1152 KB Correct.
5 Correct 33 ms 1104 KB Correct.
6 Correct 6 ms 3676 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 23120 KB Correct.
2 Correct 576 ms 1508 KB Correct.
3 Correct 467 ms 1636 KB Correct.
4 Correct 501 ms 1612 KB Correct.
5 Correct 355 ms 1488 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1624 KB Correct.
2 Correct 26 ms 1628 KB Correct.
3 Correct 26 ms 1612 KB Correct.
4 Correct 24 ms 4700 KB Correct.
5 Correct 28 ms 1116 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1624 KB Correct.
2 Correct 23 ms 1484 KB Correct.
3 Correct 46 ms 30564 KB Correct.
4 Correct 18 ms 3228 KB Correct.
5 Correct 26 ms 1104 KB Correct.
6 Correct 30 ms 1364 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 1796 KB Correct.
2 Correct 34 ms 1584 KB Correct.
3 Correct 2231 ms 30724 KB Correct.
4 Correct 1621 ms 8688 KB Correct.
5 Correct 1243 ms 48240 KB Correct.
6 Correct 483 ms 22864 KB Correct.
7 Correct 1590 ms 8708 KB Correct.
8 Correct 1401 ms 3004 KB Correct.
9 Correct 252 ms 1904 KB Correct.
10 Correct 274 ms 1676 KB Correct.
11 Correct 1281 ms 2260 KB Correct.
12 Correct 293 ms 1796 KB Correct.
13 Correct 292 ms 1944 KB Correct.
14 Correct 1467 ms 11100 KB Correct.
15 Correct 1846 ms 4056 KB Correct.
16 Correct 271 ms 1876 KB Correct.
17 Correct 316 ms 1784 KB Correct.
18 Correct 325 ms 2124 KB Correct.
19 Correct 967 ms 2388 KB Correct.
20 Correct 20 ms 604 KB Correct.
21 Correct 24 ms 920 KB Correct.
22 Correct 28 ms 2496 KB Correct.

Subtask #8
0.0 / 3.0

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