oj.uz

Submission #862825

# Submission time Handle Problem Language Result Execution time Memory
862825 2023-10-19T05:09:20 Z Berryisbetter Cyberland (APIO23_cyberland) C++17
97 / 100
 2960 ms 991560 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, 65) + 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 259 ms 592 KB Correct.
2 Correct 257 ms 596 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 768 ms 5724 KB Correct.
2 Correct 918 ms 5972 KB Correct.
3 Correct 877 ms 5864 KB Correct.
4 Correct 921 ms 5864 KB Correct.
5 Correct 901 ms 5700 KB Correct.
6 Correct 941 ms 53248 KB Correct.
7 Correct 1248 ms 47636 KB Correct.
8 Correct 504 ms 96460 KB Correct.
9 Correct 776 ms 1148 KB Correct.
10 Correct 766 ms 1088 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1232 ms 6300 KB Correct.
2 Correct 1183 ms 6684 KB Correct.
3 Correct 1092 ms 6216 KB Correct.
4 Correct 1041 ms 1380 KB Correct.
5 Correct 1056 ms 1260 KB Correct.
6 Correct 264 ms 43796 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 906 ms 345684 KB Correct.
2 Correct 880 ms 7140 KB Correct.
3 Correct 786 ms 7508 KB Correct.
4 Correct 834 ms 7168 KB Correct.
5 Correct 772 ms 1320 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 499 ms 5936 KB Correct.
2 Correct 536 ms 6220 KB Correct.
3 Correct 553 ms 5852 KB Correct.
4 Correct 682 ms 46140 KB Correct.
5 Correct 455 ms 1404 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 812 ms 6148 KB Correct.
2 Correct 660 ms 5948 KB Correct.
3 Correct 1057 ms 376912 KB Correct.
4 Correct 586 ms 43456 KB Correct.
5 Correct 723 ms 1208 KB Correct.
6 Correct 742 ms 6104 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 894 ms 6800 KB Correct.
2 Correct 117 ms 11244 KB Correct.
3 Correct 1768 ms 273196 KB Correct.
4 Correct 1298 ms 82568 KB Correct.
5 Correct 2805 ms 451156 KB Correct.
6 Correct 1251 ms 338240 KB Correct.
7 Correct 1287 ms 72332 KB Correct.
8 Correct 1071 ms 14956 KB Correct.
9 Correct 765 ms 6856 KB Correct.
10 Correct 770 ms 6476 KB Correct.
11 Correct 1089 ms 5508 KB Correct.
12 Correct 858 ms 6888 KB Correct.
13 Correct 826 ms 7408 KB Correct.
14 Correct 1056 ms 66356 KB Correct.
15 Correct 1112 ms 29924 KB Correct.
16 Correct 819 ms 7548 KB Correct.
17 Correct 916 ms 7348 KB Correct.
18 Correct 891 ms 6868 KB Correct.
19 Correct 2139 ms 8856 KB Correct.
20 Correct 67 ms 1076 KB Correct.
21 Correct 66 ms 5476 KB Correct.
22 Correct 96 ms 34588 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1988 ms 14200 KB Correct.
2 Correct 289 ms 23444 KB Correct.
3 Incorrect 2960 ms 991560 KB Wrong Answer.
4 Halted 0 ms 0 KB -