oj.uz

Submission #748978

# Submission time Handle Problem Language Result Execution time Memory
748978 2023-05-27T08:38:56 Z penguin133 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 92564 KB 
#include <bits/stdc++.h>
using namespace std;

#include "cyberland.h"
typedef long double ld;
typedef long long ll;
#define fi first
#define se second
#define pi pair<int, int>
#define pii pair<int, pi>
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

vector <pi> adj[100000];
double dist[69][100000];

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) {
	K = min(K, 68);
    priority_queue <pair<double, pi>, vector<pair<double, pi> >, greater<pair<double, pi> > > pq;
    pq.push({0.0, {0, 0}});
    for(int i=0;i<N;i++)for(int j=0;j<=K;j++)dist[j][i] = 1e18;
    dist[0][0] = 0;
    for(int i=0;i<N;i++)adj[i].clear();
    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]});
	}
	while(!pq.empty()){
		double a = pq.top().fi; int b = pq.top().se.fi, c = pq.top().se.se;
		pq.pop();
		if(dist[c][b] < a || b == H)continue;
		for(auto [i, j] : adj[b]){
			
			if(arr[i] == 0){
				if(dist[c][i])dist[c][i] = 0, pq.push({0, {i, c}});
			}
			else if(dist[c][i] > a + j)dist[c][i] = a + j, pq.push({dist[c][i], {i, c}});
			if(arr[i] == 2 && c < K){
				if(dist[c+1][i] > (a + ((double)j)) / 2)dist[c+1][i] = (a + ((double)j)) / 2, pq.push({dist[c+1][i], {i, c+1}});
			}
		}
	}
	double ans = 1e18;
	for(int i=0;i<=K;i++)ans = min(ans, dist[i][H]);
	if(ans > 1e15)return -1;
	else return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2900 KB Correct.
2 Correct 24 ms 2892 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3284 KB Correct.
2 Correct 26 ms 3196 KB Correct.
3 Correct 24 ms 3232 KB Correct.
4 Correct 25 ms 3200 KB Correct.
5 Correct 24 ms 3156 KB Correct.
6 Correct 25 ms 5904 KB Correct.
7 Correct 33 ms 5844 KB Correct.
8 Correct 15 ms 8916 KB Correct.
9 Correct 23 ms 2912 KB Correct.
10 Correct 24 ms 2908 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3144 KB Correct.
2 Correct 26 ms 3200 KB Correct.
3 Correct 25 ms 3256 KB Correct.
4 Correct 26 ms 3040 KB Correct.
5 Correct 25 ms 2912 KB Correct.
6 Correct 8 ms 5332 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 20692 KB Correct.
2 Correct 519 ms 3200 KB Correct.
3 Correct 418 ms 3192 KB Correct.
4 Correct 447 ms 3292 KB Correct.
5 Correct 325 ms 2916 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3156 KB Correct.
2 Correct 23 ms 3156 KB Correct.
3 Correct 24 ms 3204 KB Correct.
4 Correct 27 ms 6004 KB Correct.
5 Correct 20 ms 2908 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3260 KB Correct.
2 Correct 21 ms 3244 KB Correct.
3 Correct 48 ms 26292 KB Correct.
4 Correct 17 ms 5204 KB Correct.
5 Correct 22 ms 2900 KB Correct.
6 Correct 22 ms 3284 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 3716 KB Correct.
2 Correct 34 ms 4176 KB Correct.
3 Correct 1561 ms 23876 KB Correct.
4 Correct 1118 ms 8748 KB Correct.
5 Correct 911 ms 32496 KB Correct.
6 Correct 362 ms 17476 KB Correct.
7 Correct 1157 ms 8920 KB Correct.
8 Correct 1000 ms 4184 KB Correct.
9 Correct 248 ms 3872 KB Correct.
10 Correct 262 ms 4088 KB Correct.
11 Correct 951 ms 3540 KB Correct.
12 Correct 273 ms 3860 KB Correct.
13 Correct 262 ms 3996 KB Correct.
14 Correct 964 ms 11448 KB Correct.
15 Correct 1307 ms 5656 KB Correct.
16 Correct 241 ms 3704 KB Correct.
17 Correct 303 ms 3992 KB Correct.
18 Correct 303 ms 3800 KB Correct.
19 Correct 930 ms 4132 KB Correct.
20 Correct 20 ms 2980 KB Correct.
21 Correct 24 ms 3508 KB Correct.
22 Correct 24 ms 4684 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 805 ms 5440 KB Correct.
2 Correct 86 ms 6016 KB Correct.
3 Correct 558 ms 63016 KB Correct.
4 Correct 2714 ms 7596 KB Correct.
5 Correct 2412 ms 92564 KB Correct.
6 Correct 973 ms 45508 KB Correct.
7 Execution timed out 3036 ms 30156 KB Time limit exceeded
8 Halted 0 ms 0 KB -