oj.uz

Submission #862833

# Submission time Handle Problem Language Result Execution time Memory
862833 2023-10-19T05:31:21 Z Berryisbetter Cyberland (APIO23_cyberland) C++17
97 / 100
 2718 ms 917088 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long double;
using vll = vector<ll>;
using vvll = vector<vll>;
const ll INF = 1e16;

vll v; vector<vector<pair<ll, ll>>>g;
ll h, n;
void dfs(ll x) {
	if (v[x]++) return;
	if ((int)x % (int)n == h) return;
	for (auto i : g[x]) {
		dfs(i.first);
	}
}
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) {
	ll m = M, k = min(K, 60) + 1; h = H, n = N;
	v = vll(n * k); g = vector<vector<pair<ll, ll>>>(n * k);
	for (ll j = 0; j < k; j++) {
		for (ll i = 0; i < m; i++) {
			g[x[i] + j * n].push_back({ y[i] + j * n, c[i] * (long double)1.0 / (1ll << (long long)j)});
			g[y[i] + j * n].push_back({ x[i] + j * n, c[i] * (long double)1.0 / (1ll << (long long)j) });
			if (j && arr[y[i]] == 2) {
				g[x[i] + j * n].push_back({ y[i] + (j - 1) * n, c[i] * (long double)1.0 / (1ll << (long long)j) });
			}
			if (j && arr[x[i]] == 2) {
				g[y[i] + j * n].push_back({ x[i] + (j - 1) * n, c[i] * (long double)1.0 / (1ll << (long long)j) });
			}
		}
	}
	for (ll i = 0; i < k; i++) {
		dfs(i * n);
	}
	vll save = v;
	v = vll(n * k, INF);
	priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> q;
	for (ll i = 0; i < k; i++) {
		q.push({ 0,i * n }); v[i * n] = 0;

	}
	for (ll j = 0; j < k; j++) {
		for (ll i = 0; i < n; i++) {
			if (arr[i] == 0 && save[i + j * n]) {
				q.push({ 0, i + j * n });
				v[i + j * n] = 0;
			}
		}
	}
	save = vll(n * k);
	while (q.size()) {
		ll ce = q.top().second; q.pop();
		if (((int)ce % (int)n) == h) {
			continue;
		}
		if (!save[ce]++) {
			for (auto i : g[ce]) {
				if (v[i.first] > v[ce] + i.second) {
					v[i.first] = v[ce] + i.second;
					q.push({ v[i.first],i.first });
				}
			}
		}
	}
	if (v[h] >= INF) {
		return -1;
	}
	return v[h];
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 564 KB Correct.
2 Correct 235 ms 612 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 741 ms 5724 KB Correct.
2 Correct 810 ms 5980 KB Correct.
3 Correct 777 ms 5500 KB Correct.
4 Correct 798 ms 5864 KB Correct.
5 Correct 787 ms 5828 KB Correct.
6 Correct 882 ms 53252 KB Correct.
7 Correct 1138 ms 47640 KB Correct.
8 Correct 480 ms 96496 KB Correct.
9 Correct 713 ms 1148 KB Correct.
10 Correct 719 ms 1436 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 915 ms 6464 KB Correct.
2 Correct 915 ms 6684 KB Correct.
3 Correct 832 ms 6272 KB Correct.
4 Correct 803 ms 1612 KB Correct.
5 Correct 804 ms 1208 KB Correct.
6 Correct 222 ms 43800 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 720 ms 346428 KB Correct.
2 Correct 703 ms 7384 KB Correct.
3 Correct 627 ms 7644 KB Correct.
4 Correct 660 ms 7152 KB Correct.
5 Correct 603 ms 1240 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 6020 KB Correct.
2 Correct 531 ms 6004 KB Correct.
3 Correct 518 ms 5660 KB Correct.
4 Correct 647 ms 46060 KB Correct.
5 Correct 420 ms 1208 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 590 ms 6476 KB Correct.
2 Correct 476 ms 5924 KB Correct.
3 Correct 718 ms 376672 KB Correct.
4 Correct 445 ms 43188 KB Correct.
5 Correct 509 ms 1088 KB Correct.
6 Correct 534 ms 6048 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 736 ms 6992 KB Correct.
2 Correct 100 ms 11220 KB Correct.
3 Correct 1735 ms 273044 KB Correct.
4 Correct 1256 ms 82504 KB Correct.
5 Correct 2606 ms 450548 KB Correct.
6 Correct 1243 ms 338776 KB Correct.
7 Correct 1243 ms 72192 KB Correct.
8 Correct 985 ms 15160 KB Correct.
9 Correct 606 ms 6828 KB Correct.
10 Correct 593 ms 6572 KB Correct.
11 Correct 958 ms 5612 KB Correct.
12 Correct 647 ms 6900 KB Correct.
13 Correct 639 ms 7108 KB Correct.
14 Correct 1018 ms 66376 KB Correct.
15 Correct 1086 ms 29976 KB Correct.
16 Correct 644 ms 7232 KB Correct.
17 Correct 715 ms 7296 KB Correct.
18 Correct 710 ms 6860 KB Correct.
19 Correct 1769 ms 8672 KB Correct.
20 Correct 51 ms 1016 KB Correct.
21 Correct 49 ms 5608 KB Correct.
22 Correct 101 ms 34592 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1476 ms 13596 KB Correct.
2 Correct 222 ms 21752 KB Correct.
3 Incorrect 2718 ms 917088 KB Wrong Answer.
4 Halted 0 ms 0 KB -