oj.uz

Submission #748984

# Submission time Handle Problem Language Result Execution time Memory
748984 2023-05-27T08:43:33 Z penguin133 Cyberland (APIO23_cyberland) C++17
44 / 100
 59 ms 26284 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[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[i] == 2 && i < K){
					if(dist[i+1][ii] > (a + ((double)j)) / 2)dist[i+1][i] = (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
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 3024 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3208 KB Correct.
2 Correct 29 ms 3128 KB Correct.
3 Correct 30 ms 3184 KB Correct.
4 Correct 26 ms 3220 KB Correct.
5 Correct 35 ms 3156 KB Correct.
6 Correct 27 ms 5908 KB Correct.
7 Correct 31 ms 5792 KB Correct.
8 Correct 16 ms 8916 KB Correct.
9 Correct 24 ms 2920 KB Correct.
10 Correct 24 ms 2900 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3156 KB Correct.
2 Correct 29 ms 3188 KB Correct.
3 Correct 30 ms 3236 KB Correct.
4 Correct 28 ms 2900 KB Correct.
5 Correct 30 ms 2904 KB Correct.
6 Correct 8 ms 5460 KB Correct.

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 20556 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3284 KB Correct.
2 Correct 27 ms 3156 KB Correct.
3 Correct 26 ms 3240 KB Correct.
4 Correct 27 ms 5972 KB Correct.
5 Correct 22 ms 2852 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3312 KB Correct.
2 Correct 22 ms 3248 KB Correct.
3 Correct 59 ms 26284 KB Correct.
4 Correct 18 ms 5236 KB Correct.
5 Correct 25 ms 2924 KB Correct.
6 Correct 26 ms 3276 KB Correct.

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 3156 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 3668 KB Wrong Answer.
2 Halted 0 ms 0 KB -