Submission #984978

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
984978	2024-05-17T08:53:00 Z	javotaz	Cyberland (APIO23_cyberland)	C++17	100 / 100	1539 ms	73568 KB

cyberland

// 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;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	4440 KB	Correct.
2	Correct	17 ms	4440 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	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.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	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.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	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.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	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.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	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.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	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.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	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.

Submission #984978

Compilation message