답안 #984978

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
984978 2024-05-17T08:53:00 Z javotaz 사이버랜드 (APIO23_cyberland) C++17
100 / 100
1539 ms 73568 KB
// In the Name of Allah

#include<bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")

typedef long long ll;
typedef pair<double, int> pd;

#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
#define pp pop_back
#define all(x) x.begin(), x.end()

const int N = 1e5 + 12, K = 77;
vector<pii> g[N];
int n, m, k, h, a[N];
double ans;
bool mrk[N][K], t[N]; 

void dfs(int u) {
	t[u] = true;
	if (u == h)
		return;
	for (auto i: g[u])
		if (!t[i.F])
			dfs(i.F);
}

void find_ans() {
	dfs(0);
	ans = 1e18;
	if (!t[h]) { 
		ans = -1;
		return;
	}
	priority_queue<pd, vector<pd>, greater<pd>> q[k + 2];
	q[0].push({0, 0});
	for (int i = 1; i < n; i++)
		if (!a[i] && t[i])
			q[0].push({0, i});
	int pt = 0;
	while (pt <= k) {
		if (q[pt].empty()) {
			++pt;
			continue;
		}
		auto [w, u] = q[pt].top();
		q[pt].pop();
		if (u == h) {
			ans = min(ans, w);
			mrk[u][pt] = true;
		}
		if (mrk[u][pt]) 
			continue;
		mrk[u][pt] = true;
		for (auto i: g[u])
			if (a[i.F]) {
				if (!mrk[i.F][pt])
					q[pt].push({w + i.S, i.F});
				if (a[i.F] == 2)
					q[pt + 1].push({(w + i.S) / 2, i.F});
			}
	}
}

double solve(int ns, int ms, int ks, int hs, vector<int> xs, vector<int> ys, vector<int> ws, vector<int> as) {
	n = ns, m = ms, k = min(ks, 75), h = hs;
	for (int i = 0; i < m; i++)
		g[xs[i]].pb({ys[i], ws[i]}), g[ys[i]].pb({xs[i], ws[i]});
	for (int i = 0; i < n; i++)
		a[i] = as[i];
	find_ans();
	for (int i = 0; i < n; i++) {
		g[i].clear();
		t[i] = false;
		for (int j = 0; j <= k; ++j)
			mrk[i][j] = false;
	}
	return ans;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 4440 KB Correct.
2 Correct 17 ms 4440 KB Correct.
# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 4740 KB Correct.
2 Correct 20 ms 4684 KB Correct.
3 Correct 19 ms 4700 KB Correct.
4 Correct 20 ms 4700 KB Correct.
5 Correct 24 ms 4700 KB Correct.
6 Correct 19 ms 5980 KB Correct.
7 Correct 29 ms 5724 KB Correct.
8 Correct 15 ms 7260 KB Correct.
9 Correct 21 ms 4444 KB Correct.
10 Correct 19 ms 4528 KB Correct.
# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 4700 KB Correct.
2 Correct 22 ms 4696 KB Correct.
3 Correct 20 ms 4696 KB Correct.
4 Correct 21 ms 4444 KB Correct.
5 Correct 22 ms 4444 KB Correct.
6 Correct 7 ms 5724 KB Correct.
# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 15108 KB Correct.
2 Correct 76 ms 7004 KB Correct.
3 Correct 67 ms 7872 KB Correct.
4 Correct 86 ms 7936 KB Correct.
5 Correct 53 ms 5472 KB Correct.
# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 6748 KB Correct.
2 Correct 20 ms 6748 KB Correct.
3 Correct 20 ms 6740 KB Correct.
4 Correct 23 ms 7616 KB Correct.
5 Correct 18 ms 4552 KB Correct.
# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 6748 KB Correct.
2 Correct 18 ms 6744 KB Correct.
3 Correct 33 ms 15948 KB Correct.
4 Correct 14 ms 7512 KB Correct.
5 Correct 19 ms 4560 KB Correct.
6 Correct 19 ms 4700 KB Correct.
# 결과 실행 시간 메모리 Grader output
1 Correct 121 ms 7140 KB Correct.
2 Correct 26 ms 7516 KB Correct.
3 Correct 466 ms 21172 KB Correct.
4 Correct 211 ms 10192 KB Correct.
5 Correct 498 ms 36896 KB Correct.
6 Correct 393 ms 37392 KB Correct.
7 Correct 228 ms 10096 KB Correct.
8 Correct 162 ms 7204 KB Correct.
9 Correct 107 ms 8120 KB Correct.
10 Correct 99 ms 8168 KB Correct.
11 Correct 143 ms 6740 KB Correct.
12 Correct 110 ms 8308 KB Correct.
13 Correct 130 ms 8188 KB Correct.
14 Correct 228 ms 13852 KB Correct.
15 Correct 211 ms 8780 KB Correct.
16 Correct 116 ms 8604 KB Correct.
17 Correct 123 ms 8388 KB Correct.
18 Correct 118 ms 8236 KB Correct.
19 Correct 219 ms 6992 KB Correct.
20 Correct 7 ms 4752 KB Correct.
21 Correct 11 ms 4960 KB Correct.
22 Correct 43 ms 8276 KB Correct.
# 결과 실행 시간 메모리 Grader output
1 Correct 259 ms 7716 KB Correct.
2 Correct 52 ms 8424 KB Correct.
3 Correct 280 ms 21508 KB Correct.
4 Correct 254 ms 7728 KB Correct.
5 Correct 1133 ms 67808 KB Correct.
6 Correct 925 ms 73568 KB Correct.
7 Correct 531 ms 12904 KB Correct.
8 Correct 205 ms 6860 KB Correct.
9 Correct 222 ms 8696 KB Correct.
10 Correct 205 ms 8900 KB Correct.
11 Correct 201 ms 5664 KB Correct.
12 Correct 241 ms 8884 KB Correct.
13 Correct 266 ms 9084 KB Correct.
14 Correct 1539 ms 35740 KB Correct.
15 Correct 866 ms 16104 KB Correct.
16 Correct 390 ms 10144 KB Correct.
17 Correct 238 ms 7060 KB Correct.
18 Correct 236 ms 8908 KB Correct.
19 Correct 268 ms 9012 KB Correct.
20 Correct 230 ms 8992 KB Correct.
21 Correct 513 ms 7748 KB Correct.
22 Correct 10 ms 4696 KB Correct.
23 Correct 16 ms 5236 KB Correct.
24 Correct 87 ms 12888 KB Correct.