oj.uz

Submission #749877

# Submission time Handle Problem Language Result Execution time Memory
749877 2023-05-28T19:47:05 Z 1ne Cyberland (APIO23_cyberland) C++17
97 / 100
 790 ms 2097152 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]});
	 }
	 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 21 ms 400 KB Correct.
2 Correct 22 ms 540 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 704 KB Correct.
2 Correct 26 ms 720 KB Correct.
3 Correct 24 ms 724 KB Correct.
4 Correct 25 ms 596 KB Correct.
5 Correct 25 ms 680 KB Correct.
6 Correct 21 ms 3864 KB Correct.
7 Correct 27 ms 3832 KB Correct.
8 Correct 14 ms 7508 KB Correct.
9 Correct 24 ms 340 KB Correct.
10 Correct 25 ms 428 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 652 KB Correct.
2 Correct 26 ms 684 KB Correct.
3 Correct 24 ms 708 KB Correct.
4 Correct 27 ms 340 KB Correct.
5 Correct 27 ms 340 KB Correct.
6 Correct 8 ms 3184 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 21248 KB Correct.
2 Correct 197 ms 688 KB Correct.
3 Correct 172 ms 912 KB Correct.
4 Correct 185 ms 660 KB Correct.
5 Correct 136 ms 532 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 704 KB Correct.
2 Correct 27 ms 680 KB Correct.
3 Correct 26 ms 692 KB Correct.
4 Correct 25 ms 3692 KB Correct.
5 Correct 24 ms 416 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 596 KB Correct.
2 Correct 24 ms 688 KB Correct.
3 Correct 52 ms 27904 KB Correct.
4 Correct 19 ms 2468 KB Correct.
5 Correct 26 ms 412 KB Correct.
6 Correct 25 ms 680 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 600 KB Correct.
2 Correct 24 ms 852 KB Correct.
3 Correct 505 ms 26456 KB Correct.
4 Correct 301 ms 6920 KB Correct.
5 Correct 728 ms 17088 KB Correct.
6 Correct 284 ms 8020 KB Correct.
7 Correct 305 ms 6736 KB Correct.
8 Correct 226 ms 1612 KB Correct.
9 Correct 149 ms 752 KB Correct.
10 Correct 157 ms 696 KB Correct.
11 Correct 216 ms 792 KB Correct.
12 Correct 163 ms 752 KB Correct.
13 Correct 160 ms 720 KB Correct.
14 Correct 291 ms 8540 KB Correct.
15 Correct 274 ms 2440 KB Correct.
16 Correct 156 ms 676 KB Correct.
17 Correct 190 ms 624 KB Correct.
18 Correct 175 ms 772 KB Correct.
19 Correct 543 ms 688 KB Correct.
20 Correct 13 ms 340 KB Correct.
21 Correct 12 ms 600 KB Correct.
22 Correct 23 ms 980 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 790 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -