oj.uz

Submission #749880

# Submission time Handle Problem Language Result Execution time Memory
749880 2023-05-28T19:54:22 Z 1ne Cyberland (APIO23_cyberland) C++17
97 / 100
 1835 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(1000,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;
	 				if (u.second - 2 >=0){
	 					dist[x.first][u.second - 2] = min(dist[x.first][u.second - 2],dist[x.first][u.second - 1]);
	 				}
	 				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 19 ms 468 KB Correct.
2 Correct 19 ms 412 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 724 KB Correct.
2 Correct 25 ms 692 KB Correct.
3 Correct 25 ms 724 KB Correct.
4 Correct 26 ms 696 KB Correct.
5 Correct 26 ms 724 KB Correct.
6 Correct 24 ms 3864 KB Correct.
7 Correct 32 ms 3836 KB Correct.
8 Correct 18 ms 7392 KB Correct.
9 Correct 33 ms 420 KB Correct.
10 Correct 26 ms 340 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 668 KB Correct.
2 Correct 27 ms 596 KB Correct.
3 Correct 24 ms 704 KB Correct.
4 Correct 30 ms 408 KB Correct.
5 Correct 28 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 104 ms 21324 KB Correct.
2 Correct 148 ms 680 KB Correct.
3 Correct 136 ms 724 KB Correct.
4 Correct 146 ms 680 KB Correct.
5 Correct 105 ms 532 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 692 KB Correct.
2 Correct 27 ms 704 KB Correct.
3 Correct 30 ms 692 KB Correct.
4 Correct 24 ms 3596 KB Correct.
5 Correct 24 ms 340 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 724 KB Correct.
2 Correct 27 ms 664 KB Correct.
3 Correct 53 ms 27924 KB Correct.
4 Correct 22 ms 2480 KB Correct.
5 Correct 26 ms 420 KB Correct.
6 Correct 26 ms 632 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 680 KB Correct.
2 Correct 21 ms 852 KB Correct.
3 Correct 413 ms 26232 KB Correct.
4 Correct 284 ms 6796 KB Correct.
5 Correct 687 ms 16616 KB Correct.
6 Correct 255 ms 7756 KB Correct.
7 Correct 270 ms 6768 KB Correct.
8 Correct 204 ms 1400 KB Correct.
9 Correct 166 ms 684 KB Correct.
10 Correct 151 ms 660 KB Correct.
11 Correct 197 ms 848 KB Correct.
12 Correct 158 ms 792 KB Correct.
13 Correct 155 ms 776 KB Correct.
14 Correct 267 ms 8524 KB Correct.
15 Correct 270 ms 2548 KB Correct.
16 Correct 144 ms 720 KB Correct.
17 Correct 182 ms 704 KB Correct.
18 Correct 171 ms 692 KB Correct.
19 Correct 526 ms 688 KB Correct.
20 Correct 11 ms 340 KB Correct.
21 Correct 12 ms 516 KB Correct.
22 Correct 21 ms 980 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1835 ms 7236 KB Correct.
2 Correct 383 ms 7520 KB Correct.
3 Incorrect 84 ms 91084 KB Wrong Answer.
4 Halted 0 ms 0 KB -