oj.uz

Submission #862822

# Submission time Handle Problem Language Result Execution time Memory
862822 2023-10-19T05:05:01 Z Berryisbetter Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 1214476 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, 80) + 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 864 KB Correct.
2 Correct 261 ms 1124 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 757 ms 6272 KB Correct.
2 Correct 923 ms 6784 KB Correct.
3 Correct 880 ms 6452 KB Correct.
4 Correct 906 ms 6832 KB Correct.
5 Correct 900 ms 6972 KB Correct.
6 Correct 942 ms 53884 KB Correct.
7 Correct 1248 ms 48424 KB Correct.
8 Correct 514 ms 96852 KB Correct.
9 Correct 793 ms 2252 KB Correct.
10 Correct 769 ms 2204 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1218 ms 7244 KB Correct.
2 Correct 1177 ms 7400 KB Correct.
3 Correct 1131 ms 6936 KB Correct.
4 Correct 1048 ms 2084 KB Correct.
5 Correct 1060 ms 1992 KB Correct.
6 Correct 271 ms 44048 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 918 ms 348516 KB Correct.
2 Correct 891 ms 8092 KB Correct.
3 Correct 831 ms 8352 KB Correct.
4 Correct 857 ms 8036 KB Correct.
5 Correct 777 ms 2068 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 6768 KB Correct.
2 Correct 538 ms 6792 KB Correct.
3 Correct 591 ms 6872 KB Correct.
4 Correct 701 ms 46792 KB Correct.
5 Correct 456 ms 1880 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 837 ms 7188 KB Correct.
2 Correct 668 ms 6276 KB Correct.
3 Correct 1039 ms 378720 KB Correct.
4 Correct 592 ms 43544 KB Correct.
5 Correct 721 ms 1964 KB Correct.
6 Correct 777 ms 6892 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 895 ms 7872 KB Correct.
2 Correct 130 ms 11644 KB Correct.
3 Correct 1799 ms 275860 KB Correct.
4 Correct 1311 ms 84760 KB Correct.
5 Correct 2786 ms 452316 KB Correct.
6 Correct 1259 ms 340112 KB Correct.
7 Correct 1318 ms 73152 KB Correct.
8 Correct 1074 ms 16272 KB Correct.
9 Correct 765 ms 7960 KB Correct.
10 Correct 797 ms 7644 KB Correct.
11 Correct 1067 ms 6648 KB Correct.
12 Correct 864 ms 7912 KB Correct.
13 Correct 840 ms 8504 KB Correct.
14 Correct 1068 ms 68692 KB Correct.
15 Correct 1111 ms 32060 KB Correct.
16 Correct 819 ms 8444 KB Correct.
17 Correct 924 ms 8208 KB Correct.
18 Correct 897 ms 7668 KB Correct.
19 Correct 2114 ms 10432 KB Correct.
20 Correct 68 ms 1104 KB Correct.
21 Correct 66 ms 5764 KB Correct.
22 Correct 96 ms 34816 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2473 ms 20128 KB Correct.
2 Correct 356 ms 29668 KB Correct.
3 Execution timed out 3074 ms 1214476 KB Time limit exceeded
4 Halted 0 ms 0 KB -