Submission #748976

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
748976	2023-05-27T08:28:21 Z	model_code	Cyberland (APIO23_cyberland)	C++17	100 / 100	1613 ms	15836 KB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << (x) << endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;

const int MAXN = 100005, MAXM = 100005;
const double inf = 1e16;

int n, m, k, h, arr_[MAXN];
vector<pair<int, int> > g[MAXN];
double dist[MAXN], dist_[MAXN];
bool vis[MAXN];
void dfs(int u) {
	vis[u] = true;
	for (auto i : g[u]) {
		if (!vis[i.fi] && i.fi != h) dfs(i.fi);
	}
}

priority_queue<pair<double, int> > que;
double dijk(int x) {
	while (!que.empty()) que.pop();
	for (int i = 0; i < n; i++) vis[i] = false, que.push(mp(-dist[i], i));
	for (int i = 0; i < n; i++) {
		while (!que.empty() && vis[que.top().se]) que.pop();
		pair<double, int> pi = que.top();
		int u = pi.se;
		vis[u] = true, que.pop();
		for (auto i : g[u]) {
			int v = i.fi;
			if (v == h) continue;
			if (dist[v] > dist[u] + 1.0 * i.se) {
				dist[v] = dist[u] + 1.0 * i.se;
				que.push(mp(-dist[v], v));
			}
		}
	}
	for (int i = 0; i < n; i++) {
		dist_[i] = inf;
		for (auto j : g[i]) {
			if (arr_[j.fi] == 2 && dist[j.fi] < inf / 2)
                dist_[i] = min(dist_[i], dist[j.fi] / 2.0 + j.se);
		}
	}
	double res = x ? dist_[h] : inf;
	for (auto i : g[h]) res = min(res, dist[i.fi] + i.se);
	for (int i = 0; i < n; i++) dist[i] = i == h ? inf : dist_[i];
	return res;
}

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
	n = N, m = M, k = K, h = H;
	for (int i = 0; i < n; i++) {
		arr_[i] = arr[i];
		dist[i] = i ? inf : 0.0;
		g[i].clear();
		vis[i] = false;
	}
	for (int i = 0; i < n; i++) g[i].clear();
	for (int i = 0; i < m; i++) {
		g[x[i]].pb(mp(y[i], c[i]));
		g[y[i]].pb(mp(x[i], c[i]));
	}
	dfs(0);
	for (int i = 0; i < n; i++) {
		if (vis[i] && !arr[i]) dist[i] = 0.0;
	}
	double ans = inf;
	k = min(k, 70);
	for (int i = k; i >= 0; i--) ans = min(ans, dijk(i));
	return ans >= inf / 2 ? -1 : ans;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	36 ms	2764 KB	Correct.
2	Correct	38 ms	2724 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	128 ms	2772 KB	Correct.
2	Correct	163 ms	2792 KB	Correct.
3	Correct	142 ms	2804 KB	Correct.
4	Correct	153 ms	3072 KB	Correct.
5	Correct	151 ms	2960 KB	Correct.
6	Correct	146 ms	3724 KB	Correct.
7	Correct	193 ms	3732 KB	Correct.
8	Correct	79 ms	4892 KB	Correct.
9	Correct	124 ms	2720 KB	Correct.
10	Correct	106 ms	2732 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	145 ms	2796 KB	Correct.
2	Correct	166 ms	2828 KB	Correct.
3	Correct	130 ms	2804 KB	Correct.
4	Correct	110 ms	2844 KB	Correct.
5	Correct	109 ms	2724 KB	Correct.
6	Correct	34 ms	3540 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	315 ms	9016 KB	Correct.
2	Correct	216 ms	2792 KB	Correct.
3	Correct	195 ms	2844 KB	Correct.
4	Correct	206 ms	2848 KB	Correct.
5	Correct	138 ms	2720 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	140 ms	2964 KB	Correct.
2	Correct	150 ms	2844 KB	Correct.
3	Correct	144 ms	2836 KB	Correct.
4	Correct	151 ms	3904 KB	Correct.
5	Correct	129 ms	2720 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	151 ms	2908 KB	Correct.
2	Correct	128 ms	2816 KB	Correct.
3	Correct	382 ms	10952 KB	Correct.
4	Correct	144 ms	3644 KB	Correct.
5	Correct	118 ms	2720 KB	Correct.
6	Correct	137 ms	2912 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	223 ms	2848 KB	Correct.
2	Correct	29 ms	2900 KB	Correct.
3	Correct	776 ms	13016 KB	Correct.
4	Correct	434 ms	5124 KB	Correct.
5	Correct	458 ms	9576 KB	Correct.
6	Correct	165 ms	7624 KB	Correct.
7	Correct	447 ms	5144 KB	Correct.
8	Correct	368 ms	3172 KB	Correct.
9	Correct	204 ms	2948 KB	Correct.
10	Correct	193 ms	2804 KB	Correct.
11	Correct	328 ms	3040 KB	Correct.
12	Correct	236 ms	2972 KB	Correct.
13	Correct	210 ms	2876 KB	Correct.
14	Correct	420 ms	7880 KB	Correct.
15	Correct	398 ms	4068 KB	Correct.
16	Correct	209 ms	2812 KB	Correct.
17	Correct	259 ms	2916 KB	Correct.
18	Correct	219 ms	2888 KB	Correct.
19	Correct	562 ms	2832 KB	Correct.
20	Correct	14 ms	2712 KB	Correct.
21	Correct	22 ms	2744 KB	Correct.
22	Correct	13 ms	3156 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	446 ms	2904 KB	Correct.
2	Correct	49 ms	2892 KB	Correct.
3	Correct	1359 ms	15836 KB	Correct.
4	Correct	502 ms	3532 KB	Correct.
5	Correct	931 ms	9572 KB	Correct.
6	Correct	323 ms	7624 KB	Correct.
7	Correct	726 ms	7328 KB	Correct.
8	Correct	489 ms	3064 KB	Correct.
9	Correct	404 ms	2952 KB	Correct.
10	Correct	413 ms	2904 KB	Correct.
11	Correct	176 ms	2944 KB	Correct.
12	Correct	472 ms	2908 KB	Correct.
13	Correct	425 ms	2892 KB	Correct.
14	Correct	1613 ms	8824 KB	Correct.
15	Correct	1524 ms	7996 KB	Correct.
16	Correct	720 ms	4924 KB	Correct.
17	Correct	558 ms	3200 KB	Correct.
18	Correct	412 ms	2912 KB	Correct.
19	Correct	481 ms	2964 KB	Correct.
20	Correct	442 ms	2920 KB	Correct.
21	Correct	1190 ms	2928 KB	Correct.
22	Correct	24 ms	2644 KB	Correct.
23	Correct	39 ms	2772 KB	Correct.
24	Correct	24 ms	3156 KB	Correct.

Submission #748976

Compilation message