oj.uz

Submission #862819

# Submission time Handle Problem Language Result Execution time Memory
862819 2023-10-19T05:02:26 Z Berryisbetter Cyberland (APIO23_cyberland) C++17
97 / 100
 2766 ms 917020 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, 60) + 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 263 ms 1048 KB Correct.
2 Correct 257 ms 588 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 750 ms 5588 KB Correct.
2 Correct 908 ms 5980 KB Correct.
3 Correct 864 ms 5620 KB Correct.
4 Correct 901 ms 6184 KB Correct.
5 Correct 906 ms 5880 KB Correct.
6 Correct 933 ms 53256 KB Correct.
7 Correct 1228 ms 47708 KB Correct.
8 Correct 520 ms 96340 KB Correct.
9 Correct 788 ms 1244 KB Correct.
10 Correct 777 ms 1392 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1205 ms 6524 KB Correct.
2 Correct 1204 ms 6508 KB Correct.
3 Correct 1096 ms 6160 KB Correct.
4 Correct 1044 ms 1164 KB Correct.
5 Correct 1059 ms 1580 KB Correct.
6 Correct 261 ms 43824 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 888 ms 346656 KB Correct.
2 Correct 880 ms 8240 KB Correct.
3 Correct 794 ms 8480 KB Correct.
4 Correct 838 ms 8056 KB Correct.
5 Correct 789 ms 2292 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 485 ms 5860 KB Correct.
2 Correct 541 ms 6340 KB Correct.
3 Correct 563 ms 5860 KB Correct.
4 Correct 698 ms 46056 KB Correct.
5 Correct 471 ms 1052 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 835 ms 6260 KB Correct.
2 Correct 668 ms 5924 KB Correct.
3 Correct 1008 ms 376948 KB Correct.
4 Correct 579 ms 44500 KB Correct.
5 Correct 726 ms 1420 KB Correct.
6 Correct 743 ms 6000 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 883 ms 6856 KB Correct.
2 Correct 117 ms 11328 KB Correct.
3 Correct 1773 ms 275732 KB Correct.
4 Correct 1281 ms 84860 KB Correct.
5 Correct 2659 ms 452752 KB Correct.
6 Correct 1186 ms 340116 KB Correct.
7 Correct 1331 ms 73268 KB Correct.
8 Correct 1075 ms 16108 KB Correct.
9 Correct 777 ms 7644 KB Correct.
10 Correct 766 ms 7368 KB Correct.
11 Correct 1068 ms 6476 KB Correct.
12 Correct 862 ms 7916 KB Correct.
13 Correct 819 ms 8272 KB Correct.
14 Correct 1053 ms 68668 KB Correct.
15 Correct 1114 ms 32088 KB Correct.
16 Correct 830 ms 8388 KB Correct.
17 Correct 920 ms 8616 KB Correct.
18 Correct 885 ms 7480 KB Correct.
19 Correct 2102 ms 10364 KB Correct.
20 Correct 68 ms 1108 KB Correct.
21 Correct 65 ms 5580 KB Correct.
22 Correct 93 ms 34760 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1838 ms 13488 KB Correct.
2 Correct 243 ms 21732 KB Correct.
3 Incorrect 2766 ms 917020 KB Wrong Answer.
4 Halted 0 ms 0 KB -