oj.uz

Submission #862826

# Submission time Handle Problem Language Result Execution time Memory
862826 2023-10-19T05:13:08 Z Berryisbetter Cyberland (APIO23_cyberland) C++17
97 / 100
 1443 ms 657916 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using ll = 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, 68) + 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 = k-1; i >= 0; 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 81 ms 600 KB Correct.
2 Correct 81 ms 532 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 4332 KB Correct.
2 Correct 337 ms 4684 KB Correct.
3 Correct 326 ms 4252 KB Correct.
4 Correct 339 ms 4012 KB Correct.
5 Correct 335 ms 4176 KB Correct.
6 Correct 403 ms 30880 KB Correct.
7 Correct 533 ms 33788 KB Correct.
8 Correct 241 ms 60624 KB Correct.
9 Correct 304 ms 1032 KB Correct.
10 Correct 280 ms 920 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 4116 KB Correct.
2 Correct 403 ms 4384 KB Correct.
3 Correct 351 ms 4040 KB Correct.
4 Correct 334 ms 896 KB Correct.
5 Correct 339 ms 956 KB Correct.
6 Correct 102 ms 27008 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 210820 KB Correct.
2 Correct 350 ms 4868 KB Correct.
3 Correct 298 ms 4876 KB Correct.
4 Correct 322 ms 4724 KB Correct.
5 Correct 324 ms 948 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 4224 KB Correct.
2 Correct 263 ms 4032 KB Correct.
3 Correct 253 ms 4020 KB Correct.
4 Correct 372 ms 28084 KB Correct.
5 Correct 198 ms 1056 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 4748 KB Correct.
2 Correct 223 ms 3736 KB Correct.
3 Correct 466 ms 233628 KB Correct.
4 Correct 228 ms 26564 KB Correct.
5 Correct 240 ms 864 KB Correct.
6 Correct 259 ms 4092 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 4232 KB Correct.
2 Correct 50 ms 6328 KB Correct.
3 Correct 985 ms 171864 KB Correct.
4 Correct 609 ms 51108 KB Correct.
5 Correct 1443 ms 248764 KB Correct.
6 Correct 658 ms 177632 KB Correct.
7 Correct 655 ms 45404 KB Correct.
8 Correct 431 ms 9244 KB Correct.
9 Correct 297 ms 4796 KB Correct.
10 Correct 306 ms 4168 KB Correct.
11 Correct 444 ms 3568 KB Correct.
12 Correct 334 ms 4560 KB Correct.
13 Correct 325 ms 4772 KB Correct.
14 Correct 567 ms 40296 KB Correct.
15 Correct 467 ms 18532 KB Correct.
16 Correct 319 ms 4740 KB Correct.
17 Correct 367 ms 4836 KB Correct.
18 Correct 340 ms 4396 KB Correct.
19 Correct 845 ms 5148 KB Correct.
20 Correct 25 ms 860 KB Correct.
21 Correct 25 ms 3544 KB Correct.
22 Correct 51 ms 18088 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 791 ms 9200 KB Correct.
2 Correct 133 ms 13660 KB Correct.
3 Incorrect 1075 ms 657916 KB Wrong Answer.
4 Halted 0 ms 0 KB -