Submission #804494

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
804494	2023-08-03T09:08:01 Z	MadokaMagicaFan	Cyberland (APIO23_cyberland)	C++17	100 / 100	747 ms	20048 KB

cyberland

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
#define sz(v) ((int)(v).size())
#define pb push_back

const int N = 1e5;
vector<array<ll, 2>> adj[N];
bitset<N> v, ps;
ll mind1[N], mind2[N], sme[N];
ld md[N];
ll inf = 1e18;

void
dfs(int x, int h) {
	if (x == h) return;
	if (ps[x]) return;
	ps[x] = 1;

	for (auto u : adj[x])
		dfs(u[0], h);
}

double
solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr)
{
	for (int i = 0; i < n; ++i) {
		sme[i] = inf;
		mind2[i] = inf;
		mind1[i] = 0;
		while (sz(adj[i]))
			adj[i].pop_back();
	}
	v = 0;
	ps = 0;

	if (h == 0) return 0;
	for (int i = 0; i < m; ++i) {
		adj[x[i]].pb({y[i], c[i]});
		if (y[i] != h)
			sme[x[i]] = min(sme[x[i]], (ll)c[i]);
		adj[y[i]].pb({x[i], c[i]});
		if (x[i] != h)
			sme[y[i]] = min(sme[y[i]], (ll)c[i]);
	}

	dfs(0, h);
	priority_queue<array<ll, 2>> q;
	for (int i = 1; i < n; ++i) {
		if (arr[i] == 0 && ps[i]) {
			q.push({0, i});
			mind1[i] = 0;
		}
		else
			mind1[i] = inf;
	}
	q.push({0, 0});

	while (sz(q)) {
		auto u = q.top();
		q.pop();
		if (v[u[1]]) continue;
		if (u[1] == h) continue;
		v[u[1]] = 1;

		for (auto x : adj[u[1]]) {
			if (mind1[u[1]]+ x[1] < mind1[x[0]]) {
				mind1[x[0]] = mind1[u[1]]+ x[1];
				q.push({-mind1[x[0]], x[0]});
			}
		}
	}

	if (mind1[h] > 1e17) return -1;

	long double ans = mind1[h];
	while (sz(q)) q.pop();
	mind2[h] = 0;
	q.push({0, h});

	v = 0;
	while (sz(q)) {
		auto u = q.top();
		q.pop();
		if (v[u[1]]) continue;
		v[u[1]] = 1;

		for (auto x : adj[u[1]]) {
			if (mind2[u[1]]+ x[1] < mind2[x[0]]) {
				mind2[x[0]] = mind2[u[1]]+ x[1];
				q.push({-mind2[x[0]], x[0]});
			}
		}
	}

	int cn = min(k, 200);
	for (int i = 0; i < n; ++i) {
		md[i] = mind1[i];
	}
	priority_queue<pair<ld, int>> qq;
	while (cn--) {
		while (sz(qq)) qq.pop();
		v = 0;
		for (int i = 1; i < n; ++i) {
			if (arr[i] == 2 && ps[i]) {
				qq.push({-(md[i] / ((ld) 2)), i});
			}
		}

		while (sz(qq)) {
			auto u = qq.top();
			qq.pop();
			if (v[u.second]) continue;
			if (u.second == h) continue;
			v[u.second] = 1;

			for (auto x : adj[u.second]) {
				if (-u.first + ((ld)x[1]) < md[x[0]]) {
					md[x[0]] = -u.first + ((ld)x[1]);
					qq.push({-md[x[0]], x[0]});
				}
			}
		}

		ans = min(ans, md[h]);
	}

	return ans;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	76 ms	2772 KB	Correct.
2	Correct	79 ms	3112 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	2988 KB	Correct.
2	Correct	26 ms	2916 KB	Correct.
3	Correct	25 ms	2924 KB	Correct.
4	Correct	26 ms	2936 KB	Correct.
5	Correct	26 ms	2892 KB	Correct.
6	Correct	22 ms	3980 KB	Correct.
7	Correct	29 ms	3984 KB	Correct.
8	Correct	13 ms	5156 KB	Correct.
9	Correct	32 ms	2776 KB	Correct.
10	Correct	31 ms	2772 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	2900 KB	Correct.
2	Correct	26 ms	2924 KB	Correct.
3	Correct	26 ms	2888 KB	Correct.
4	Correct	33 ms	2788 KB	Correct.
5	Correct	33 ms	2776 KB	Correct.
6	Correct	7 ms	3796 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	87 ms	10452 KB	Correct.
2	Correct	81 ms	3924 KB	Correct.
3	Correct	57 ms	3872 KB	Correct.
4	Correct	67 ms	3892 KB	Correct.
5	Correct	52 ms	3652 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	3028 KB	Correct.
2	Correct	22 ms	3028 KB	Correct.
3	Correct	22 ms	3028 KB	Correct.
4	Correct	22 ms	4488 KB	Correct.
5	Correct	23 ms	2760 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	3028 KB	Correct.
2	Correct	20 ms	3028 KB	Correct.
3	Correct	33 ms	10936 KB	Correct.
4	Correct	18 ms	4100 KB	Correct.
5	Correct	26 ms	2772 KB	Correct.
6	Correct	22 ms	2984 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	50 ms	3012 KB	Correct.
2	Correct	11 ms	3168 KB	Correct.
3	Correct	214 ms	17404 KB	Correct.
4	Correct	164 ms	7964 KB	Correct.
5	Correct	182 ms	13972 KB	Correct.
6	Correct	69 ms	11084 KB	Correct.
7	Correct	149 ms	8008 KB	Correct.
8	Correct	126 ms	5268 KB	Correct.
9	Correct	46 ms	4004 KB	Correct.
10	Correct	55 ms	4004 KB	Correct.
11	Correct	118 ms	4888 KB	Correct.
12	Correct	49 ms	4060 KB	Correct.
13	Correct	50 ms	3996 KB	Correct.
14	Correct	146 ms	10832 KB	Correct.
15	Correct	135 ms	6480 KB	Correct.
16	Correct	50 ms	4072 KB	Correct.
17	Correct	57 ms	4124 KB	Correct.
18	Correct	51 ms	4024 KB	Correct.
19	Correct	141 ms	4996 KB	Correct.
20	Correct	6 ms	2804 KB	Correct.
21	Correct	5 ms	2936 KB	Correct.
22	Correct	7 ms	3668 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	143 ms	3012 KB	Correct.
2	Correct	25 ms	3292 KB	Correct.
3	Correct	141 ms	20048 KB	Correct.
4	Correct	166 ms	5868 KB	Correct.
5	Correct	747 ms	14020 KB	Correct.
6	Correct	235 ms	11124 KB	Correct.
7	Correct	211 ms	10464 KB	Correct.
8	Correct	164 ms	5108 KB	Correct.
9	Correct	124 ms	3936 KB	Correct.
10	Correct	126 ms	3916 KB	Correct.
11	Correct	643 ms	4040 KB	Correct.
12	Correct	167 ms	3964 KB	Correct.
13	Correct	136 ms	3948 KB	Correct.
14	Correct	386 ms	12704 KB	Correct.
15	Correct	469 ms	11200 KB	Correct.
16	Correct	268 ms	7628 KB	Correct.
17	Correct	175 ms	5308 KB	Correct.
18	Correct	124 ms	4016 KB	Correct.
19	Correct	165 ms	4076 KB	Correct.
20	Correct	143 ms	4068 KB	Correct.
21	Correct	416 ms	4992 KB	Correct.
22	Correct	12 ms	2836 KB	Correct.
23	Correct	12 ms	2804 KB	Correct.
24	Correct	14 ms	3556 KB	Correct.

Submission #804494

Compilation message