oj.uz

Submission #1000981

# Submission time Handle Problem Language Result Execution time Memory
1000981 2024-06-18T12:13:03 Z 0npata Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 102472 KB 
#include "cyberland.h"
#include<bits/stdc++.h>

using namespace std;

#define vec vector
#define int long long
#define float long double

const float INF = 1e18;

double solve(int32_t N, int32_t M, int32_t K, int32_t H, std::vector<int32_t> x, std::vector<int32_t> y, std::vector<int32_t> c, std::vector<int32_t> t) {
	float ans = INF;


	int n = N;
	int m = M;
	int k = K;

	priority_queue<pair<pair<int, float>, int>, vector<pair<pair<int, float>, int>>, greater<pair<pair<int, float>, int>>> pq;
	vec<vec<bool>> vis(k+2, vec<bool>(n, false));

	vec<vec<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]});
	}

	pq.push({{0, 0}, 0});

	vec<bool> dfs_vis(n, false);
	vec<int> stk{0};
	dfs_vis[0] = true;
	while(stk.size() > 0) {
		int u = stk.back();
		stk.pop_back();

		if(u==H) continue;

		if(t[u] == 0) {
			pq.push({{0, 0}, u});
		}

		for(auto e : g[u]) {
			if(dfs_vis[e.first]) continue;
			stk.push_back(e.first);
			dfs_vis[e.first] = true;
		}
	}

	while(pq.size() > 0) {
		pair<pair<int, float>, int> cur = pq.top();
		pq.pop();

		int ck = cur.first.first;
		float d = cur.first.second;
		int u = cur.second;


		if(ck > k) break;

		if(u == H) {
			ans = min(ans, d);
			continue;
		}
		if(vis[ck][u]) {
			continue;
		}
		vis[ck][u] = true;

		for(auto e : g[u]) {
			int v = e.first;
			float w = e.second;

			pq.push({{ck, d+w}, v});
			if(t[v] == 2) {
				pq.push({{ck+1, (d+w)/(float)2}, v});
			}
		}
	}

	if(ans == INF) return -1;

	return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 592 KB Correct.
2 Correct 39 ms 344 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 604 KB Correct.
2 Correct 32 ms 604 KB Correct.
3 Correct 30 ms 604 KB Correct.
4 Correct 32 ms 604 KB Correct.
5 Correct 32 ms 604 KB Correct.
6 Correct 29 ms 1696 KB Correct.
7 Correct 38 ms 1840 KB Correct.
8 Correct 17 ms 3096 KB Correct.
9 Correct 30 ms 348 KB Correct.
10 Correct 33 ms 524 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 600 KB Correct.
2 Correct 38 ms 600 KB Correct.
3 Correct 36 ms 696 KB Correct.
4 Correct 34 ms 348 KB Correct.
5 Correct 37 ms 600 KB Correct.
6 Correct 8 ms 2136 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 8148 KB Correct.
2 Correct 408 ms 884 KB Correct.
3 Correct 355 ms 1456 KB Correct.
4 Correct 383 ms 1616 KB Correct.
5 Correct 255 ms 1364 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 604 KB Correct.
2 Correct 29 ms 604 KB Correct.
3 Correct 30 ms 712 KB Correct.
4 Correct 33 ms 2312 KB Correct.
5 Correct 25 ms 348 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 720 KB Correct.
2 Correct 29 ms 728 KB Correct.
3 Correct 31 ms 9052 KB Correct.
4 Correct 21 ms 2296 KB Correct.
5 Correct 31 ms 348 KB Correct.
6 Correct 32 ms 760 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 684 ms 708 KB Correct.
2 Correct 108 ms 1056 KB Correct.
3 Correct 991 ms 14028 KB Correct.
4 Correct 710 ms 5128 KB Correct.
5 Correct 2459 ms 23288 KB Correct.
6 Correct 2230 ms 21340 KB Correct.
7 Correct 733 ms 4860 KB Correct.
8 Correct 638 ms 2740 KB Correct.
9 Correct 577 ms 1740 KB Correct.
10 Correct 566 ms 1776 KB Correct.
11 Correct 595 ms 2568 KB Correct.
12 Correct 570 ms 1772 KB Correct.
13 Correct 609 ms 1728 KB Correct.
14 Correct 691 ms 8156 KB Correct.
15 Correct 670 ms 3740 KB Correct.
16 Correct 594 ms 1836 KB Correct.
17 Correct 668 ms 1788 KB Correct.
18 Correct 654 ms 1848 KB Correct.
19 Correct 1307 ms 2744 KB Correct.
20 Correct 35 ms 348 KB Correct.
21 Correct 41 ms 604 KB Correct.
22 Correct 185 ms 2872 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3057 ms 102472 KB Time limit exceeded
2 Halted 0 ms 0 KB -