oj.uz

Submission #862827

# Submission time Handle Problem Language Result Execution time Memory
862827 2023-10-19T05:14:45 Z Berryisbetter Cyberland (APIO23_cyberland) C++17
97 / 100
 1445 ms 723552 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, 75) + 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 85 ms 596 KB Correct.
2 Correct 80 ms 592 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 4332 KB Correct.
2 Correct 344 ms 4712 KB Correct.
3 Correct 323 ms 4372 KB Correct.
4 Correct 344 ms 4016 KB Correct.
5 Correct 344 ms 4108 KB Correct.
6 Correct 393 ms 30888 KB Correct.
7 Correct 526 ms 33864 KB Correct.
8 Correct 243 ms 60640 KB Correct.
9 Correct 281 ms 904 KB Correct.
10 Correct 282 ms 884 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 4124 KB Correct.
2 Correct 378 ms 4400 KB Correct.
3 Correct 350 ms 4044 KB Correct.
4 Correct 332 ms 876 KB Correct.
5 Correct 343 ms 1040 KB Correct.
6 Correct 100 ms 27060 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 209416 KB Correct.
2 Correct 331 ms 4840 KB Correct.
3 Correct 312 ms 4872 KB Correct.
4 Correct 317 ms 4488 KB Correct.
5 Correct 284 ms 908 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 4720 KB Correct.
2 Correct 278 ms 4196 KB Correct.
3 Correct 261 ms 4096 KB Correct.
4 Correct 357 ms 27872 KB Correct.
5 Correct 196 ms 856 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 4444 KB Correct.
2 Correct 225 ms 3924 KB Correct.
3 Correct 471 ms 233736 KB Correct.
4 Correct 235 ms 26720 KB Correct.
5 Correct 244 ms 908 KB Correct.
6 Correct 258 ms 4264 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 4212 KB Correct.
2 Correct 51 ms 6332 KB Correct.
3 Correct 989 ms 171604 KB Correct.
4 Correct 613 ms 51068 KB Correct.
5 Correct 1445 ms 249136 KB Correct.
6 Correct 661 ms 177952 KB Correct.
7 Correct 620 ms 45372 KB Correct.
8 Correct 427 ms 9384 KB Correct.
9 Correct 309 ms 4716 KB Correct.
10 Correct 298 ms 4084 KB Correct.
11 Correct 453 ms 3568 KB Correct.
12 Correct 334 ms 4500 KB Correct.
13 Correct 340 ms 4852 KB Correct.
14 Correct 629 ms 40112 KB Correct.
15 Correct 488 ms 18512 KB Correct.
16 Correct 342 ms 4816 KB Correct.
17 Correct 386 ms 4728 KB Correct.
18 Correct 341 ms 4104 KB Correct.
19 Correct 891 ms 5284 KB Correct.
20 Correct 25 ms 864 KB Correct.
21 Correct 26 ms 3708 KB Correct.
22 Correct 52 ms 18116 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1022 ms 10008 KB Correct.
2 Correct 174 ms 14552 KB Correct.
3 Incorrect 1289 ms 723552 KB Wrong Answer.
4 Halted 0 ms 0 KB -