oj.uz

Submission #862832

# Submission time Handle Problem Language Result Execution time Memory
862832 2023-10-19T05:28:58 Z Berryisbetter Cyberland (APIO23_cyberland) C++17
97 / 100
 2831 ms 768436 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, 50) + 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] * 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 = 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 260 ms 596 KB Correct.
2 Correct 264 ms 868 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 763 ms 5736 KB Correct.
2 Correct 908 ms 5980 KB Correct.
3 Correct 865 ms 5572 KB Correct.
4 Correct 895 ms 5936 KB Correct.
5 Correct 950 ms 6016 KB Correct.
6 Correct 958 ms 53364 KB Correct.
7 Correct 1245 ms 47888 KB Correct.
8 Correct 511 ms 96404 KB Correct.
9 Correct 822 ms 1204 KB Correct.
10 Correct 768 ms 1388 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1213 ms 6336 KB Correct.
2 Correct 1195 ms 6668 KB Correct.
3 Correct 1145 ms 6100 KB Correct.
4 Correct 1044 ms 1412 KB Correct.
5 Correct 1045 ms 1448 KB Correct.
6 Correct 262 ms 43796 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 896 ms 347380 KB Correct.
2 Correct 898 ms 7136 KB Correct.
3 Correct 787 ms 7608 KB Correct.
4 Correct 835 ms 7232 KB Correct.
5 Correct 778 ms 1292 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 485 ms 5976 KB Correct.
2 Correct 541 ms 5996 KB Correct.
3 Correct 587 ms 6108 KB Correct.
4 Correct 768 ms 45884 KB Correct.
5 Correct 452 ms 1056 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 838 ms 6264 KB Correct.
2 Correct 669 ms 6188 KB Correct.
3 Correct 1090 ms 376856 KB Correct.
4 Correct 598 ms 43164 KB Correct.
5 Correct 726 ms 1288 KB Correct.
6 Correct 742 ms 6016 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 897 ms 6992 KB Correct.
2 Correct 124 ms 11184 KB Correct.
3 Correct 1847 ms 273060 KB Correct.
4 Correct 1331 ms 82656 KB Correct.
5 Correct 2831 ms 451708 KB Correct.
6 Correct 1259 ms 339076 KB Correct.
7 Correct 1349 ms 72232 KB Correct.
8 Correct 1110 ms 14800 KB Correct.
9 Correct 797 ms 6804 KB Correct.
10 Correct 777 ms 6544 KB Correct.
11 Correct 1076 ms 5500 KB Correct.
12 Correct 881 ms 6788 KB Correct.
13 Correct 850 ms 7436 KB Correct.
14 Correct 1127 ms 66324 KB Correct.
15 Correct 1126 ms 29808 KB Correct.
16 Correct 846 ms 7304 KB Correct.
17 Correct 928 ms 7248 KB Correct.
18 Correct 896 ms 6716 KB Correct.
19 Correct 2188 ms 8444 KB Correct.
20 Correct 69 ms 1020 KB Correct.
21 Correct 67 ms 5584 KB Correct.
22 Correct 99 ms 34560 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1518 ms 11288 KB Correct.
2 Correct 209 ms 18468 KB Correct.
3 Incorrect 2326 ms 768436 KB Wrong Answer.
4 Halted 0 ms 0 KB -