oj.uz

Submission #749152

# Submission time Handle Problem Language Result Execution time Memory
749152 2023-05-27T12:13:21 Z gun_gan Cyberland (APIO23_cyberland) C++17
97 / 100
 1540 ms 16604 KB 
#include <bits/stdc++.h>
#include "cyberland.h"
using namespace std;
typedef long long ll;

double solve(int N, int M, int K, int H, vector<int> x, vector<int>
y, vector<int> c, vector<int> arr) {
	vector<vector<pair<int,int>>> g(N);
	for(int i = 0; i < M; i++) {
		g[x[i]].push_back({y[i], c[i]});
		g[y[i]].push_back({x[i], c[i]});
	}
	priority_queue<pair<double,int>> pq;

	vector<double> dd(N, 1e18);
	
	{
		dd[0] = 0;
		pq.push({0, 0});

		while(!pq.empty()) {
			auto [x, v] = pq.top(); pq.pop();
			x = -x;
			if(dd[v] < x) continue;
			for(auto [u, w] : g[v]) {
				if(dd[u] > x + w && u != H) {
					dd[u] = x + w;
					pq.push({-dd[u], u});
				}
			} 
		}
	}

	vector<array<double, 2>> d(N, {1e18, 1e18});

	arr[0] = 0;
	for(int i = 0; i < N; i++) if(!arr[i] && dd[i] == 1e18) arr[i] = 1;

	{
		for(int i = 0; i < N; i++) {
			if(!arr[i] && dd[i] != 1e18) {
				d[i][1] = 0;
				pq.push({0, i});
			}
		}

		while(!pq.empty()) {
			auto [x, v] = pq.top(); pq.pop();
			x = -x;
			if(d[v][1] < x) continue;
			for(auto [u, w] : g[v]) {
				if(d[u][1] > x + w && u != H) {
					d[u][1] = x + w;
					pq.push({-d[u][1], u});
				}
			} 
		}
	}


	double res = 1e18;

	for(auto [u, w] : g[H]) {
		res = min(res, d[u][1] + w);
	}

	for(int k = 1; k <= min(60, K); k++) {
		vector<array<double,2>> nd(N, {1e18, 1e18});

		priority_queue<pair<double,pair<int, int>>> pq;
		for(int i = 0; i < N; i++) {
			nd[i][0] = min(d[i][0], d[i][1]);
			if(arr[i] == 2 && nd[i][0] != 1e18) {
				nd[i][0] = min(nd[i][0], d[i][1] / 2);
			}
			if(nd[i][0] != 1e18) pq.push({-nd[i][0], {i, 0}});
		}

		while(!pq.empty()) {
			auto [x, p] = pq.top(); 
			auto [v, c] = p;
			pq.pop();

			x = -x;
			if(nd[v][c] < x) continue;
			for(auto [u, w] : g[v]) {
				if(nd[u][c | 1] > x + w && u != H) {
					nd[u][c | 1] = x + w;
					pq.push({-nd[u][c | 1], {u, c | 1}});
				}
			} 
		}

		swap(nd, d);
		for(auto [u, w] : g[H]) {
			res = min(res, min(d[u][0], d[u][1]) + w);
		}
	}

	if(res == 1e18) res = -1;
	return res;
}	

// int main() {
// 	cin.tie(0); ios_base::sync_with_stdio(0);

// 	// cout << fixed << setprecision(1) << solve(4, 4, 30, 3, {0, 0, 1, 2}, {1, 2, 3, 3}, {5, 4, 2, 4}, {1, 0, 2, 1}) << '\n';
// 	// cout << fixed << setprecision(1) << solve(3, 2, 30, 2, {1, 2}, {2, 0}, {12, 4}, {1, 2, 1}) << '\n';
// 	cout << fixed << setprecision(1) << solve(4, 3, 3, 3, {0, 1, 2}, {1, 2, 3}, {11, 1, 10}, {1, 1, 2, 1}) << '\n';
// }

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 376 KB Correct.
2 Correct 45 ms 460 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 448 KB Correct.
2 Correct 340 ms 448 KB Correct.
3 Correct 327 ms 624 KB Correct.
4 Correct 345 ms 588 KB Correct.
5 Correct 334 ms 464 KB Correct.
6 Correct 401 ms 2112 KB Correct.
7 Correct 532 ms 2132 KB Correct.
8 Correct 228 ms 3724 KB Correct.
9 Correct 176 ms 400 KB Correct.
10 Correct 179 ms 460 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 660 KB Correct.
2 Correct 373 ms 652 KB Correct.
3 Correct 336 ms 656 KB Correct.
4 Correct 205 ms 408 KB Correct.
5 Correct 199 ms 412 KB Correct.
6 Correct 91 ms 1856 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 8552 KB Correct.
2 Correct 208 ms 576 KB Correct.
3 Correct 181 ms 452 KB Correct.
4 Correct 199 ms 592 KB Correct.
5 Correct 122 ms 396 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 512 KB Correct.
2 Correct 160 ms 440 KB Correct.
3 Correct 177 ms 496 KB Correct.
4 Correct 226 ms 1704 KB Correct.
5 Correct 90 ms 404 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 460 KB Correct.
2 Correct 157 ms 476 KB Correct.
3 Correct 54 ms 10192 KB Correct.
4 Correct 159 ms 1616 KB Correct.
5 Correct 123 ms 340 KB Correct.
6 Correct 183 ms 488 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 460 KB Correct.
2 Correct 33 ms 552 KB Correct.
3 Correct 1041 ms 16560 KB Correct.
4 Correct 615 ms 4132 KB Correct.
5 Correct 693 ms 9592 KB Correct.
6 Correct 279 ms 6212 KB Correct.
7 Correct 602 ms 4284 KB Correct.
8 Correct 472 ms 972 KB Correct.
9 Correct 183 ms 432 KB Correct.
10 Correct 181 ms 456 KB Correct.
11 Correct 416 ms 688 KB Correct.
12 Correct 214 ms 596 KB Correct.
13 Correct 198 ms 508 KB Correct.
14 Correct 522 ms 8400 KB Correct.
15 Correct 515 ms 2404 KB Correct.
16 Correct 192 ms 460 KB Correct.
17 Correct 224 ms 460 KB Correct.
18 Correct 218 ms 504 KB Correct.
19 Correct 642 ms 508 KB Correct.
20 Correct 12 ms 384 KB Correct.
21 Correct 18 ms 412 KB Correct.
22 Correct 21 ms 852 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 544 KB Correct.
2 Correct 56 ms 468 KB Correct.
3 Incorrect 1540 ms 16604 KB Wrong Answer.
4 Halted 0 ms 0 KB -