oj.uz

Submission #831606

# Submission time Handle Problem Language Result Execution time Memory
831606 2023-08-20T11:14:41 Z pavement Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 107868 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using ld = long double;
using diii = tuple<ld, int, int, bool>;

#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define ppb pop_back

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, 1000);
	bool vis[N];
	ld dist[N][K + 1][2];
	vector<ii> adj[N];
	queue<int> Q;
	priority_queue<diii, vector<diii>, greater<diii> > pq;
	for (int i = 0; i < N; i++) {
		vis[i] = 0;
		for (int j = 0; j <= K; j++) {
			dist[i][j][0] = dist[i][j][1] = (ld)1e18;
		}
	}
	for (int i = 0; i < M; i++) {
		adj[x[i]].eb(y[i], c[i]);
		adj[y[i]].eb(x[i], c[i]);
	}
	vis[0] = 1;
	Q.push(0);
	while (!Q.empty()) {
		int v = Q.front();
		Q.pop();
		for (auto [u, w] : adj[v]) {
			if (!vis[u] && u != H) {
				vis[u] = 1;
				Q.push(u);
			}
		}
	}
	for (int i = 0; i < N; i++) {
		if (vis[i] && (arr[i] == 0 || i == 0)) {
			dist[i][K][0] = dist[i][K][1] = 0;
			pq.emplace(0, i, K, 0);
		}
	}
	while (!pq.empty()) {
		auto [d, v, k, jd] = pq.top();
		pq.pop();
		if (d != dist[v][k][jd]) continue;
		if (v == H) continue;
		if (arr[v] == 2 && k && !jd) {
			if (d / (ld)2 < dist[v][k - 1][1]) {
				dist[v][k - 1][1] = d / (ld)2;
				pq.emplace(dist[v][k - 1][1], v, k - 1, 1);
			}
		}
		for (auto [u, w] : adj[v]) {
			if (d + w < dist[u][k][0]) {
				dist[u][k][0] = d + w;
				pq.emplace(dist[u][k][0], u, k, 0);
			}
		}
	}
	ld ret = min(dist[H][0][0], dist[H][0][1]);
	for (int i = 1; i <= K; i++) ret = min({ret, dist[H][i][0], dist[H][i][1]});
	return ret == (ld)1e18 ? -1 : ret;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 664 KB Correct.
2 Correct 27 ms 692 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2276 KB Correct.
2 Correct 42 ms 2380 KB Correct.
3 Correct 42 ms 2380 KB Correct.
4 Correct 47 ms 2384 KB Correct.
5 Correct 40 ms 2380 KB Correct.
6 Correct 41 ms 11556 KB Correct.
7 Correct 53 ms 11764 KB Correct.
8 Correct 27 ms 21768 KB Correct.
9 Correct 38 ms 1356 KB Correct.
10 Correct 35 ms 1292 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2412 KB Correct.
2 Correct 42 ms 2324 KB Correct.
3 Correct 39 ms 2356 KB Correct.
4 Correct 39 ms 1320 KB Correct.
5 Correct 38 ms 1320 KB Correct.
6 Correct 10 ms 9372 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 506 ms 67452 KB Correct.
2 Correct 589 ms 2852 KB Correct.
3 Correct 503 ms 2836 KB Correct.
4 Correct 544 ms 2836 KB Correct.
5 Correct 449 ms 1448 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 2300 KB Correct.
2 Correct 39 ms 2388 KB Correct.
3 Correct 37 ms 2392 KB Correct.
4 Correct 43 ms 11672 KB Correct.
5 Correct 35 ms 1236 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 2372 KB Correct.
2 Correct 32 ms 2244 KB Correct.
3 Correct 83 ms 82544 KB Correct.
4 Correct 26 ms 8440 KB Correct.
5 Correct 35 ms 1324 KB Correct.
6 Correct 35 ms 2388 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 4136 KB Correct.
2 Correct 66 ms 5320 KB Correct.
3 Correct 1087 ms 69148 KB Correct.
4 Correct 865 ms 20756 KB Correct.
5 Correct 2008 ms 107868 KB Correct.
6 Correct 899 ms 48844 KB Correct.
7 Correct 874 ms 19248 KB Correct.
8 Correct 869 ms 5608 KB Correct.
9 Correct 462 ms 4040 KB Correct.
10 Correct 466 ms 5124 KB Correct.
11 Correct 844 ms 3576 KB Correct.
12 Correct 505 ms 4124 KB Correct.
13 Correct 538 ms 4076 KB Correct.
14 Correct 614 ms 19932 KB Correct.
15 Correct 972 ms 9852 KB Correct.
16 Correct 469 ms 4212 KB Correct.
17 Correct 564 ms 4156 KB Correct.
18 Correct 549 ms 4176 KB Correct.
19 Correct 1387 ms 5024 KB Correct.
20 Correct 35 ms 1012 KB Correct.
21 Correct 36 ms 2236 KB Correct.
22 Correct 54 ms 5936 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3063 ms 55820 KB Time limit exceeded
2 Halted 0 ms 0 KB -