oj.uz

Submission #1000995

# Submission time Handle Problem Language Result Execution time Memory
1000995 2024-06-18T12:26:05 Z 0npata Cyberland (APIO23_cyberland) C++17
97 / 100
 2392 ms 22520 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 = min(K, 30);

	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 860 KB Correct.
2 Correct 32 ms 852 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1104 KB Correct.
2 Correct 37 ms 1372 KB Correct.
3 Correct 35 ms 1360 KB Correct.
4 Correct 35 ms 1380 KB Correct.
5 Correct 34 ms 1224 KB Correct.
6 Correct 36 ms 2456 KB Correct.
7 Correct 43 ms 2428 KB Correct.
8 Correct 21 ms 3460 KB Correct.
9 Correct 48 ms 1252 KB Correct.
10 Correct 32 ms 1208 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1312 KB Correct.
2 Correct 40 ms 1360 KB Correct.
3 Correct 36 ms 1464 KB Correct.
4 Correct 39 ms 1112 KB Correct.
5 Correct 37 ms 1112 KB Correct.
6 Correct 14 ms 2396 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 9420 KB Correct.
2 Correct 436 ms 1256 KB Correct.
3 Correct 366 ms 1344 KB Correct.
4 Correct 386 ms 1644 KB Correct.
5 Correct 242 ms 1100 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1356 KB Correct.
2 Correct 31 ms 1232 KB Correct.
3 Correct 31 ms 1476 KB Correct.
4 Correct 34 ms 3080 KB Correct.
5 Correct 25 ms 1116 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1300 KB Correct.
2 Correct 29 ms 1404 KB Correct.
3 Correct 35 ms 10068 KB Correct.
4 Correct 22 ms 2804 KB Correct.
5 Correct 32 ms 1112 KB Correct.
6 Correct 31 ms 1496 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 670 ms 1644 KB Correct.
2 Correct 108 ms 1060 KB Correct.
3 Correct 951 ms 13248 KB Correct.
4 Correct 715 ms 4332 KB Correct.
5 Correct 2392 ms 22520 KB Correct.
6 Correct 2162 ms 19952 KB Correct.
7 Correct 735 ms 3868 KB Correct.
8 Correct 647 ms 1968 KB Correct.
9 Correct 558 ms 1448 KB Correct.
10 Correct 542 ms 1580 KB Correct.
11 Correct 609 ms 2000 KB Correct.
12 Correct 567 ms 1512 KB Correct.
13 Correct 611 ms 1536 KB Correct.
14 Correct 728 ms 7496 KB Correct.
15 Correct 709 ms 3136 KB Correct.
16 Correct 616 ms 1584 KB Correct.
17 Correct 647 ms 1500 KB Correct.
18 Correct 645 ms 1640 KB Correct.
19 Correct 1315 ms 1980 KB Correct.
20 Correct 35 ms 344 KB Correct.
21 Correct 37 ms 604 KB Correct.
22 Correct 185 ms 2780 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 681 ms 1644 KB Correct.
2 Correct 108 ms 1060 KB Correct.
3 Incorrect 370 ms 13396 KB Wrong Answer.
4 Halted 0 ms 0 KB -