oj.uz

Submission #749882

# Submission time Handle Problem Language Result Execution time Memory
749882 2023-05-28T19:56:49 Z 1ne Cyberland (APIO23_cyberland) C++17
97 / 100
 838 ms 91036 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 21 ms 476 KB Correct.
2 Correct 24 ms 404 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 704 KB Correct.
2 Correct 25 ms 692 KB Correct.
3 Correct 27 ms 676 KB Correct.
4 Correct 27 ms 596 KB Correct.
5 Correct 26 ms 708 KB Correct.
6 Correct 22 ms 3956 KB Correct.
7 Correct 28 ms 3796 KB Correct.
8 Correct 14 ms 7380 KB Correct.
9 Correct 25 ms 432 KB Correct.
10 Correct 24 ms 376 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 676 KB Correct.
2 Correct 27 ms 596 KB Correct.
3 Correct 33 ms 708 KB Correct.
4 Correct 26 ms 416 KB Correct.
5 Correct 26 ms 428 KB Correct.
6 Correct 6 ms 3156 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 21184 KB Correct.
2 Correct 193 ms 672 KB Correct.
3 Correct 174 ms 652 KB Correct.
4 Correct 196 ms 636 KB Correct.
5 Correct 133 ms 340 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 672 KB Correct.
2 Correct 29 ms 724 KB Correct.
3 Correct 25 ms 684 KB Correct.
4 Correct 24 ms 3596 KB Correct.
5 Correct 26 ms 424 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 724 KB Correct.
2 Correct 25 ms 688 KB Correct.
3 Correct 57 ms 27892 KB Correct.
4 Correct 19 ms 2468 KB Correct.
5 Correct 27 ms 392 KB Correct.
6 Correct 30 ms 780 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 604 KB Correct.
2 Correct 23 ms 852 KB Correct.
3 Correct 487 ms 26316 KB Correct.
4 Correct 323 ms 6760 KB Correct.
5 Correct 838 ms 17000 KB Correct.
6 Correct 284 ms 8020 KB Correct.
7 Correct 315 ms 6904 KB Correct.
8 Correct 224 ms 1524 KB Correct.
9 Correct 149 ms 696 KB Correct.
10 Correct 157 ms 676 KB Correct.
11 Correct 221 ms 792 KB Correct.
12 Correct 168 ms 624 KB Correct.
13 Correct 169 ms 816 KB Correct.
14 Correct 299 ms 8644 KB Correct.
15 Correct 276 ms 2536 KB Correct.
16 Correct 165 ms 700 KB Correct.
17 Correct 193 ms 716 KB Correct.
18 Correct 187 ms 784 KB Correct.
19 Correct 546 ms 688 KB Correct.
20 Correct 12 ms 364 KB Correct.
21 Correct 14 ms 592 KB Correct.
22 Correct 29 ms 1064 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 1164 KB Correct.
2 Correct 72 ms 1748 KB Correct.
3 Incorrect 94 ms 91036 KB Wrong Answer.
4 Halted 0 ms 0 KB -