oj.uz

Submission #985700

# Submission time Handle Problem Language Result Execution time Memory
985700 2024-05-18T14:38:22 Z siewjh Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 312300 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, 68);
	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 3672 KB Correct.
2 Correct 23 ms 3932 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5724 KB Correct.
2 Correct 36 ms 5724 KB Correct.
3 Correct 29 ms 5884 KB Correct.
4 Correct 30 ms 5928 KB Correct.
5 Correct 35 ms 5724 KB Correct.
6 Correct 33 ms 17004 KB Correct.
7 Correct 35 ms 16732 KB Correct.
8 Correct 18 ms 27736 KB Correct.
9 Correct 31 ms 3672 KB Correct.
10 Correct 27 ms 3712 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 5720 KB Correct.
2 Correct 31 ms 6744 KB Correct.
3 Correct 30 ms 6236 KB Correct.
4 Correct 30 ms 4480 KB Correct.
5 Correct 30 ms 4444 KB Correct.
6 Correct 10 ms 14940 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 82288 KB Correct.
2 Correct 453 ms 7436 KB Correct.
3 Correct 397 ms 7520 KB Correct.
4 Correct 420 ms 7696 KB Correct.
5 Correct 360 ms 4716 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 5980 KB Correct.
2 Correct 29 ms 5720 KB Correct.
3 Correct 27 ms 5984 KB Correct.
4 Correct 28 ms 16756 KB Correct.
5 Correct 27 ms 3676 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6000 KB Correct.
2 Correct 24 ms 6748 KB Correct.
3 Correct 54 ms 94804 KB Correct.
4 Correct 22 ms 13400 KB Correct.
5 Correct 26 ms 4608 KB Correct.
6 Correct 31 ms 6948 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 7884 KB Correct.
2 Correct 62 ms 10048 KB Correct.
3 Correct 926 ms 123072 KB Correct.
4 Correct 753 ms 33356 KB Correct.
5 Correct 1625 ms 114968 KB Correct.
6 Correct 757 ms 88944 KB Correct.
7 Correct 709 ms 34544 KB Correct.
8 Correct 734 ms 10412 KB Correct.
9 Correct 379 ms 9336 KB Correct.
10 Correct 390 ms 8644 KB Correct.
11 Correct 733 ms 8060 KB Correct.
12 Correct 397 ms 8776 KB Correct.
13 Correct 435 ms 8724 KB Correct.
14 Correct 587 ms 63384 KB Correct.
15 Correct 704 ms 22108 KB Correct.
16 Correct 397 ms 8788 KB Correct.
17 Correct 471 ms 8816 KB Correct.
18 Correct 458 ms 8520 KB Correct.
19 Correct 1145 ms 9336 KB Correct.
20 Correct 31 ms 4368 KB Correct.
21 Correct 31 ms 6760 KB Correct.
22 Correct 50 ms 11720 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1574 ms 13864 KB Correct.
2 Correct 198 ms 18408 KB Correct.
3 Correct 1020 ms 121112 KB Correct.
4 Correct 1692 ms 17916 KB Correct.
5 Execution timed out 3030 ms 312300 KB Time limit exceeded
6 Halted 0 ms 0 KB -