oj.uz

답안 #804494

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
804494 2023-08-03T09:08:01 Z MadokaMagicaFan 사이버랜드 (APIO23_cyberland) C++17
100 / 100
 747 ms 20048 KB 
#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

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 2772 KB Correct.
2 Correct 79 ms 3112 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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.