oj.uz

Submission #862830

# Submission time Handle Problem Language Result Execution time Memory
862830 2023-10-19T05:20:35 Z Berryisbetter Cyberland (APIO23_cyberland) C++17
97 / 100
 2041 ms 843556 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, 70) + 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 121 ms 596 KB Correct.
2 Correct 121 ms 596 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 4748 KB Correct.
2 Correct 489 ms 5132 KB Correct.
3 Correct 474 ms 4744 KB Correct.
4 Correct 513 ms 5396 KB Correct.
5 Correct 486 ms 5232 KB Correct.
6 Correct 584 ms 42304 KB Correct.
7 Correct 742 ms 36964 KB Correct.
8 Correct 337 ms 74836 KB Correct.
9 Correct 423 ms 1248 KB Correct.
10 Correct 402 ms 928 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 607 ms 5424 KB Correct.
2 Correct 597 ms 5808 KB Correct.
3 Correct 548 ms 5168 KB Correct.
4 Correct 492 ms 1088 KB Correct.
5 Correct 498 ms 1616 KB Correct.
6 Correct 159 ms 35088 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 259436 KB Correct.
2 Correct 467 ms 5612 KB Correct.
3 Correct 441 ms 5516 KB Correct.
4 Correct 457 ms 5804 KB Correct.
5 Correct 384 ms 1004 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 4676 KB Correct.
2 Correct 331 ms 4616 KB Correct.
3 Correct 360 ms 4684 KB Correct.
4 Correct 487 ms 38552 KB Correct.
5 Correct 273 ms 1088 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 5076 KB Correct.
2 Correct 328 ms 4616 KB Correct.
3 Correct 504 ms 288648 KB Correct.
4 Correct 321 ms 30088 KB Correct.
5 Correct 324 ms 968 KB Correct.
6 Correct 364 ms 5340 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 521 ms 5308 KB Correct.
2 Correct 70 ms 7920 KB Correct.
3 Correct 1298 ms 211988 KB Correct.
4 Correct 874 ms 60796 KB Correct.
5 Correct 2041 ms 315600 KB Correct.
6 Correct 872 ms 203724 KB Correct.
7 Correct 835 ms 55992 KB Correct.
8 Correct 623 ms 11936 KB Correct.
9 Correct 426 ms 5860 KB Correct.
10 Correct 436 ms 5044 KB Correct.
11 Correct 606 ms 4564 KB Correct.
12 Correct 485 ms 5188 KB Correct.
13 Correct 466 ms 5800 KB Correct.
14 Correct 764 ms 52272 KB Correct.
15 Correct 668 ms 22912 KB Correct.
16 Correct 470 ms 5840 KB Correct.
17 Correct 540 ms 5772 KB Correct.
18 Correct 512 ms 5344 KB Correct.
19 Correct 1287 ms 6636 KB Correct.
20 Correct 34 ms 1020 KB Correct.
21 Correct 35 ms 4232 KB Correct.
22 Correct 67 ms 19644 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1266 ms 12204 KB Correct.
2 Correct 211 ms 17744 KB Correct.
3 Incorrect 1750 ms 843556 KB Wrong Answer.
4 Halted 0 ms 0 KB -