oj.uz

Submission #985704

# Submission time Handle Problem Language Result Execution time Memory
985704 2024-05-18T14:39:41 Z siewjh Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 311304 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef tuple<ld, int, int> t3;
const int MAXN = 100005;
const ld inf = 1e18;
vector<pair<int, int>> adj[MAXN];
bool vis[MAXN];
ld dist[MAXN][70];

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++){
		adj[i].clear(); vis[i] = 0;
		for (int j = 0; j <= K; j++) dist[i][j] = inf;
	}
	for (int i = 0; i < M; i++){
		adj[x[i]].push_back({y[i], c[i]});
		adj[y[i]].push_back({x[i], c[i]});
	}
	priority_queue<t3, vector<t3>, greater<t3>> pq;
	pq.push({0, 0, 0}); dist[0][0] = 0;
	queue<int> q;
	q.push(0); vis[0] = 1;
	while (!q.empty()){
		int x = q.front(); q.pop();
		if (x == H) continue;
		if (arr[x] == 0){
			pq.push({0, x, 0}); dist[x][0] = 0;
		}
		for (auto &[nn, nd] : adj[x])
			if (!vis[nn]){
				q.push(nn); vis[nn] = 1;
			}
	}
	while (!pq.empty()){
		ld d; int x, use; tie(d, x, use) = pq.top(); pq.pop();
		if (dist[x][use] != d) continue;
		if (x == H) continue;
		for (auto &[nn, nd] : adj[x]){
			ld fd = d + nd;
			if (dist[nn][use] > fd){
				dist[nn][use] = fd;
				pq.push({dist[nn][use], nn, use});
			}
			if (arr[nn] == 2 && use < K && dist[nn][use + 1] > fd / 2){
				dist[nn][use + 1] = fd / 2;
				pq.push({dist[nn][use + 1], nn, use + 1});
			}
		}
	}
	ld ans = inf;
	for (int use = 0; use <= K; use++) ans = min(ans, dist[H][use]);
	return (ans == inf ? -1 : ans);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3676 KB Correct.
2 Correct 26 ms 3968 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5948 KB Correct.
2 Correct 38 ms 5724 KB Correct.
3 Correct 30 ms 5884 KB Correct.
4 Correct 33 ms 5900 KB Correct.
5 Correct 30 ms 5720 KB Correct.
6 Correct 30 ms 16696 KB Correct.
7 Correct 37 ms 16728 KB Correct.
8 Correct 18 ms 27736 KB Correct.
9 Correct 28 ms 3736 KB Correct.
10 Correct 28 ms 3676 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5720 KB Correct.
2 Correct 32 ms 5720 KB Correct.
3 Correct 31 ms 5980 KB Correct.
4 Correct 30 ms 3676 KB Correct.
5 Correct 31 ms 3676 KB Correct.
6 Correct 8 ms 15192 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 82628 KB Correct.
2 Correct 450 ms 6648 KB Correct.
3 Correct 393 ms 6664 KB Correct.
4 Correct 423 ms 6648 KB Correct.
5 Correct 352 ms 3952 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 5980 KB Correct.
2 Correct 28 ms 5724 KB Correct.
3 Correct 29 ms 5980 KB Correct.
4 Correct 28 ms 16872 KB Correct.
5 Correct 25 ms 3724 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6480 KB Correct.
2 Correct 27 ms 5976 KB Correct.
3 Correct 55 ms 92852 KB Correct.
4 Correct 21 ms 12804 KB Correct.
5 Correct 38 ms 3716 KB Correct.
6 Correct 26 ms 5980 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 7732 KB Correct.
2 Correct 61 ms 9384 KB Correct.
3 Correct 939 ms 120976 KB Correct.
4 Correct 784 ms 31488 KB Correct.
5 Correct 1706 ms 114084 KB Correct.
6 Correct 807 ms 86688 KB Correct.
7 Correct 734 ms 33392 KB Correct.
8 Correct 741 ms 8460 KB Correct.
9 Correct 374 ms 8880 KB Correct.
10 Correct 388 ms 7804 KB Correct.
11 Correct 749 ms 6380 KB Correct.
12 Correct 403 ms 7888 KB Correct.
13 Correct 433 ms 7936 KB Correct.
14 Correct 640 ms 61588 KB Correct.
15 Correct 720 ms 20340 KB Correct.
16 Correct 394 ms 7640 KB Correct.
17 Correct 483 ms 7880 KB Correct.
18 Correct 461 ms 7636 KB Correct.
19 Correct 1156 ms 7808 KB Correct.
20 Correct 34 ms 4368 KB Correct.
21 Correct 32 ms 6768 KB Correct.
22 Correct 53 ms 11212 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1520 ms 13652 KB Correct.
2 Correct 203 ms 20116 KB Correct.
3 Correct 998 ms 118800 KB Correct.
4 Correct 1655 ms 16132 KB Correct.
5 Execution timed out 3017 ms 311304 KB Time limit exceeded
6 Halted 0 ms 0 KB -