oj.uz

Submission #862831

# Submission time Handle Problem Language Result Execution time Memory
862831 2023-10-19T05:21:52 Z Berryisbetter Cyberland (APIO23_cyberland) C++17
97 / 100
 2063 ms 961160 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using ll = double;
using ld = long double;

using vll = vector<ll>;
using vvll = vector<vll>;
const ld INF = 1e16;

vector<ld> 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, 80) + 1; h = H, n = N;
	v = vector<ld>(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] * 1.0 / (1ll << (long long)j) });
			g[y[i] + j * n].push_back({ x[i] + j * n, c[i] * 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] * 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] * 1.0 / (1ll << (long long)j) });
			}
		}
	}
	for (ll i = k-1; i >= 0; i--) {
		dfs(i * n);
	}
	vector<ld> save = v;
	v = vector<ld>(n * k, INF);
	priority_queue<pair<ld, ld>, vector<pair<ld, ld>>, greater<pair<ld, ld>>> 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 = vector<ld>(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 124 ms 624 KB Correct.
2 Correct 119 ms 596 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 4580 KB Correct.
2 Correct 487 ms 5148 KB Correct.
3 Correct 481 ms 4748 KB Correct.
4 Correct 499 ms 4992 KB Correct.
5 Correct 492 ms 5028 KB Correct.
6 Correct 569 ms 42680 KB Correct.
7 Correct 805 ms 36884 KB Correct.
8 Correct 351 ms 74836 KB Correct.
9 Correct 421 ms 1028 KB Correct.
10 Correct 405 ms 1212 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 667 ms 5140 KB Correct.
2 Correct 606 ms 5884 KB Correct.
3 Correct 537 ms 5360 KB Correct.
4 Correct 473 ms 1084 KB Correct.
5 Correct 483 ms 1296 KB Correct.
6 Correct 151 ms 34992 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 499 ms 258312 KB Correct.
2 Correct 487 ms 5540 KB Correct.
3 Correct 437 ms 5572 KB Correct.
4 Correct 449 ms 5832 KB Correct.
5 Correct 384 ms 992 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 4660 KB Correct.
2 Correct 335 ms 4680 KB Correct.
3 Correct 339 ms 4712 KB Correct.
4 Correct 459 ms 38552 KB Correct.
5 Correct 262 ms 940 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 5320 KB Correct.
2 Correct 317 ms 4476 KB Correct.
3 Correct 481 ms 288624 KB Correct.
4 Correct 309 ms 30072 KB Correct.
5 Correct 344 ms 1348 KB Correct.
6 Correct 360 ms 5300 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 510 ms 5340 KB Correct.
2 Correct 71 ms 7924 KB Correct.
3 Correct 1267 ms 212312 KB Correct.
4 Correct 832 ms 58636 KB Correct.
5 Correct 1986 ms 315056 KB Correct.
6 Correct 860 ms 202884 KB Correct.
7 Correct 824 ms 56060 KB Correct.
8 Correct 631 ms 11768 KB Correct.
9 Correct 425 ms 5836 KB Correct.
10 Correct 416 ms 5156 KB Correct.
11 Correct 611 ms 4488 KB Correct.
12 Correct 517 ms 5168 KB Correct.
13 Correct 458 ms 5724 KB Correct.
14 Correct 742 ms 51896 KB Correct.
15 Correct 663 ms 23200 KB Correct.
16 Correct 448 ms 5984 KB Correct.
17 Correct 509 ms 5884 KB Correct.
18 Correct 493 ms 5560 KB Correct.
19 Correct 1227 ms 6800 KB Correct.
20 Correct 39 ms 1120 KB Correct.
21 Correct 35 ms 4288 KB Correct.
22 Correct 62 ms 19708 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1405 ms 14212 KB Correct.
2 Correct 217 ms 21772 KB Correct.
3 Incorrect 2063 ms 961160 KB Wrong Answer.
4 Halted 0 ms 0 KB -