oj.uz

Submission #749878

# Submission time Handle Problem Language Result Execution time Memory
749878 2023-05-28T19:48:05 Z 1ne Cyberland (APIO23_cyberland) C++17
97 / 100
 735 ms 91084 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;

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) {
	 vector<vector<pair<int,int>>>adj(N);
	 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]});
	 }
	 K = min(100,K);	
	 queue<pair<int,int>>q;
	 q.push({0,K});
	 vector<vector<double>>dist(N,vector<double>(K + 1,1e12));
	 dist[0][K] = 0;
	 while(!q.empty()){
	 	auto u = q.front();
	 	q.pop();
	 	if (u.first == H)continue;
	 	for (auto x:adj[u.first]){
	 		long long v = x.second;
	 		if (arr[x.first] == 0){
	 			v = -dist[u.first][u.second];	
	 		}
	 		if (dist[x.first][u.second] > dist[u.first][u.second] + v){
	 			dist[x.first][u.second] = dist[u.first][u.second] + v;
	 			q.push({x.first,u.second});
	 		}
	 		if (arr[x.first] == 2 && u.second > 0){
	 			if (dist[x.first][u.second - 1] > (dist[u.first][u.second] + x.second)/2){
	 				dist[x.first][u.second - 1] = (dist[u.first][u.second] + x.second)/2;
	 				q.push({x.first,u.second - 1});
	 			}
	 			//nx = dist[u.first][u.second] + x.second)/2 + 2 * vx) / 2 + 2 * vx ) / 2 
	 		}		
	 	}
	 }
	 double ans = 1e12;
	 for (int i = 0;i<=K;++i){
	 	ans = min(ans,dist[H][i]);
	 }	
	 if (ans == 1e12)return -1;		
	 return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 448 KB Correct.
2 Correct 21 ms 468 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 724 KB Correct.
2 Correct 25 ms 692 KB Correct.
3 Correct 26 ms 724 KB Correct.
4 Correct 25 ms 700 KB Correct.
5 Correct 25 ms 680 KB Correct.
6 Correct 22 ms 3864 KB Correct.
7 Correct 29 ms 3796 KB Correct.
8 Correct 22 ms 7388 KB Correct.
9 Correct 25 ms 428 KB Correct.
10 Correct 25 ms 432 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 596 KB Correct.
2 Correct 26 ms 704 KB Correct.
3 Correct 24 ms 736 KB Correct.
4 Correct 29 ms 340 KB Correct.
5 Correct 34 ms 340 KB Correct.
6 Correct 6 ms 3156 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 21284 KB Correct.
2 Correct 209 ms 680 KB Correct.
3 Correct 168 ms 844 KB Correct.
4 Correct 189 ms 668 KB Correct.
5 Correct 149 ms 400 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 692 KB Correct.
2 Correct 28 ms 672 KB Correct.
3 Correct 26 ms 680 KB Correct.
4 Correct 25 ms 3596 KB Correct.
5 Correct 25 ms 412 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 724 KB Correct.
2 Correct 24 ms 664 KB Correct.
3 Correct 55 ms 27900 KB Correct.
4 Correct 18 ms 2468 KB Correct.
5 Correct 27 ms 528 KB Correct.
6 Correct 27 ms 684 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 696 KB Correct.
2 Correct 22 ms 852 KB Correct.
3 Correct 496 ms 26312 KB Correct.
4 Correct 322 ms 6980 KB Correct.
5 Correct 735 ms 17116 KB Correct.
6 Correct 330 ms 8140 KB Correct.
7 Correct 303 ms 6728 KB Correct.
8 Correct 274 ms 1436 KB Correct.
9 Correct 159 ms 700 KB Correct.
10 Correct 173 ms 652 KB Correct.
11 Correct 216 ms 788 KB Correct.
12 Correct 166 ms 800 KB Correct.
13 Correct 161 ms 724 KB Correct.
14 Correct 294 ms 8536 KB Correct.
15 Correct 274 ms 2444 KB Correct.
16 Correct 154 ms 672 KB Correct.
17 Correct 208 ms 832 KB Correct.
18 Correct 181 ms 700 KB Correct.
19 Correct 584 ms 700 KB Correct.
20 Correct 12 ms 340 KB Correct.
21 Correct 13 ms 592 KB Correct.
22 Correct 25 ms 1060 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 511 ms 1164 KB Correct.
2 Correct 61 ms 1748 KB Correct.
3 Incorrect 86 ms 91084 KB Wrong Answer.
4 Halted 0 ms 0 KB -