Submission #748992

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
748992	2023-05-27T08:48:16 Z	penguin133	Cyberland (APIO23_cyberland)	C++17	100 / 100	1069 ms	64392 KB

cyberland

#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[75][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, 70);
    priority_queue <pair<double, int>, vector<pair<double, int> >, greater<pair<double, int> > > pq;
    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]});
	}
	for(int i = 0; i <= K; i++){
		for(int j = 0; j < N; j++){
			if(dist[i][j] != 1e18)pq.push({dist[i][j], j});
		}
		while(!pq.empty()){
			double a = pq.top().fi; int b = pq.top().se;
			pq.pop();
			if(dist[i][b] < a || b == H)continue;
			for(auto [ii, j] : adj[b]){
				
				if(arr[ii] == 0){
					if(dist[i][ii])dist[i][ii] = 0, pq.push({0, ii});
				}
				else if(dist[i][ii] > a + j)dist[i][ii] = a + j, pq.push({dist[i][ii], ii});
				if(arr[ii] == 2 && i < K){
					if(dist[i+1][ii] > (a + ((double)j)) / 2)dist[i+1][ii] = (a + ((double)j)) / 2;
				}
			}
		}
	}
	
	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	21 ms	2900 KB	Correct.
2	Correct	21 ms	2988 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	3156 KB	Correct.
2	Correct	29 ms	3156 KB	Correct.
3	Correct	27 ms	3212 KB	Correct.
4	Correct	31 ms	3156 KB	Correct.
5	Correct	27 ms	3180 KB	Correct.
6	Correct	25 ms	5932 KB	Correct.
7	Correct	30 ms	5844 KB	Correct.
8	Correct	18 ms	9044 KB	Correct.
9	Correct	26 ms	2896 KB	Correct.
10	Correct	24 ms	2900 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	3184 KB	Correct.
2	Correct	27 ms	3156 KB	Correct.
3	Correct	26 ms	3240 KB	Correct.
4	Correct	28 ms	2900 KB	Correct.
5	Correct	28 ms	2900 KB	Correct.
6	Correct	7 ms	5332 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	112 ms	20684 KB	Correct.
2	Correct	101 ms	3184 KB	Correct.
3	Correct	87 ms	3184 KB	Correct.
4	Correct	92 ms	3168 KB	Correct.
5	Correct	59 ms	2900 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	3248 KB	Correct.
2	Correct	25 ms	3188 KB	Correct.
3	Correct	25 ms	3232 KB	Correct.
4	Correct	25 ms	5960 KB	Correct.
5	Correct	23 ms	2900 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	3260 KB	Correct.
2	Correct	23 ms	3276 KB	Correct.
3	Correct	55 ms	26248 KB	Correct.
4	Correct	18 ms	5204 KB	Correct.
5	Correct	25 ms	2812 KB	Correct.
6	Correct	23 ms	3188 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	111 ms	3276 KB	Correct.
2	Correct	17 ms	3420 KB	Correct.
3	Correct	460 ms	22796 KB	Correct.
4	Correct	267 ms	8400 KB	Correct.
5	Correct	355 ms	16660 KB	Correct.
6	Correct	164 ms	9552 KB	Correct.
7	Correct	266 ms	8512 KB	Correct.
8	Correct	217 ms	3920 KB	Correct.
9	Correct	95 ms	3448 KB	Correct.
10	Correct	106 ms	3276 KB	Correct.
11	Correct	197 ms	3444 KB	Correct.
12	Correct	102 ms	3176 KB	Correct.
13	Correct	101 ms	3256 KB	Correct.
14	Correct	248 ms	10488 KB	Correct.
15	Correct	241 ms	5376 KB	Correct.
16	Correct	94 ms	3192 KB	Correct.
17	Correct	111 ms	3276 KB	Correct.
18	Correct	104 ms	3208 KB	Correct.
19	Correct	295 ms	3276 KB	Correct.
20	Correct	7 ms	2772 KB	Correct.
21	Correct	9 ms	3132 KB	Correct.
22	Correct	15 ms	3540 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	213 ms	3780 KB	Correct.
2	Correct	42 ms	4164 KB	Correct.
3	Correct	231 ms	64392 KB	Correct.
4	Correct	313 ms	6084 KB	Correct.
5	Correct	865 ms	27916 KB	Correct.
6	Correct	355 ms	13004 KB	Correct.
7	Correct	475 ms	16724 KB	Correct.
8	Correct	265 ms	4132 KB	Correct.
9	Correct	163 ms	3736 KB	Correct.
10	Correct	166 ms	3824 KB	Correct.
11	Correct	123 ms	3324 KB	Correct.
12	Correct	211 ms	3868 KB	Correct.
13	Correct	176 ms	3812 KB	Correct.
14	Correct	1069 ms	28352 KB	Correct.
15	Correct	858 ms	33912 KB	Correct.
16	Correct	429 ms	13768 KB	Correct.
17	Correct	296 ms	5320 KB	Correct.
18	Correct	176 ms	3780 KB	Correct.
19	Correct	209 ms	3788 KB	Correct.
20	Correct	198 ms	3796 KB	Correct.
21	Correct	625 ms	3716 KB	Correct.
22	Correct	10 ms	3028 KB	Correct.
23	Correct	15 ms	3624 KB	Correct.
24	Correct	28 ms	3924 KB	Correct.

Submission #748992

Compilation message