Submission #968387

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
968387	2024-04-23T11:17:04 Z	dubabuba	Cyberland (APIO23_cyberland)	C++17	100 / 100	1245 ms	76884 KB

cyberland

#include <bits/stdc++.h>
#include "cyberland.h"
 
#pragma GCC optimize("O3")
#pragma GCC target("lzcnt", "popcnt")
 
using namespace std;
 
typedef double dbl;
typedef vector<int> vi;
typedef long long i64;
typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair
 
template<typename T> void ono_min(T &MIN, T CMP) { if(MIN > CMP) MIN = CMP; }
template<typename T> void ono_max(T &MAX, T CMP) { if(MAX < CMP) MAX = CMP; }
 
const int mxk = 69;
const int mxn = 1e5 + 10;
vector<pii> adj[mxn];
 
dbl solve(int n, int m, int K, int h, vi x, vi y, vi c, vi arr) {
	for(int i = 0; i < n; i++)
		adj[i].clear();
	for(int i = 0; i < m; i++) {
		adj[x[i]].emplace_back(y[i], c[i]);
		adj[y[i]].emplace_back(x[i], c[i]);
	}
 
	bool in[n];
	memset(in, 0, sizeof in);
	priority_queue<pair<dbl, int>> pq[mxk];
	pq[0].push(MP(-0.0, 0));
	function<void(int)> dfs;
	dfs = [&](int u) -> void {
		if(in[u]) return;
		in[u] = 1;
		if(arr[u] == 0)
			pq[0].push(MP(-0.0, u));
		if(u == h) return;
		for(pii p : adj[u])
			if(!in[p.ff])
				dfs(p.ff);
	};
	dfs(0);
 
	dbl dis[mxk][n], ans = 1e18;
	for(int k = 0; k <= K && k < mxk; k++) {
		memset(in, 0, sizeof in);
		for(int i = 0; i < n; i++)
			dis[k][i] = 1e18;
		while(pq[k].size()) {
			dbl d = -pq[k].top().ff;
			int u = pq[k].top().ss;
			pq[k].pop();
 
			if(in[u]) continue;
			ono_min(dis[k][u], d);
			in[u] = 1;
			if(u == h) continue;
 
			for(pii p : adj[u]) {
				int v = p.ff;
				dbl w = p.ss;
				if(v * arr[v] == 0)
					continue;
				if(!in[v])
					pq[k].push(MP(-(dis[k][u] + w), v));
				if(arr[v] == 2 && k + 1 < mxk)
					pq[k + 1].push(MP(-(dis[k][u] + w) / 2.0, v));
			}
		}
		ono_min(ans, dis[k][h]);
	}
	return (ans < 1e18) ? ans : -1;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	3420 KB	Correct.
2	Correct	21 ms	3420 KB	Correct.
3	Correct	20 ms	3420 KB	Correct.
4	Correct	25 ms	3420 KB	Correct.
5	Correct	21 ms	3416 KB	Correct.
6	Correct	20 ms	8796 KB	Correct.
7	Correct	27 ms	8540 KB	Correct.
8	Correct	16 ms	14680 KB	Correct.
9	Correct	19 ms	2908 KB	Correct.
10	Correct	19 ms	2908 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	3444 KB	Correct.
2	Correct	23 ms	3420 KB	Correct.
3	Correct	23 ms	3420 KB	Correct.
4	Correct	21 ms	2904 KB	Correct.
5	Correct	22 ms	2908 KB	Correct.
6	Correct	8 ms	7772 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	92 ms	41420 KB	Correct.
2	Correct	72 ms	3680 KB	Correct.
3	Correct	66 ms	3772 KB	Correct.
4	Correct	64 ms	3704 KB	Correct.
5	Correct	42 ms	2904 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	3420 KB	Correct.
2	Correct	21 ms	3420 KB	Correct.
3	Correct	20 ms	3420 KB	Correct.
4	Correct	27 ms	8976 KB	Correct.
5	Correct	17 ms	2908 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	3320 KB	Correct.
2	Correct	19 ms	3416 KB	Correct.
3	Correct	53 ms	48812 KB	Correct.
4	Correct	16 ms	7260 KB	Correct.
5	Correct	20 ms	2908 KB	Correct.
6	Correct	20 ms	3420 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	124 ms	3932 KB	Correct.
2	Correct	23 ms	4444 KB	Correct.
3	Correct	328 ms	62052 KB	Correct.
4	Correct	212 ms	16352 KB	Correct.
5	Correct	472 ms	49552 KB	Correct.
6	Correct	370 ms	38656 KB	Correct.
7	Correct	216 ms	17468 KB	Correct.
8	Correct	151 ms	4908 KB	Correct.
9	Correct	112 ms	4024 KB	Correct.
10	Correct	104 ms	3920 KB	Correct.
11	Correct	132 ms	3596 KB	Correct.
12	Correct	109 ms	3960 KB	Correct.
13	Correct	120 ms	3868 KB	Correct.
14	Correct	250 ms	31520 KB	Correct.
15	Correct	195 ms	10528 KB	Correct.
16	Correct	115 ms	3908 KB	Correct.
17	Correct	126 ms	4012 KB	Correct.
18	Correct	121 ms	4020 KB	Correct.
19	Correct	253 ms	3828 KB	Correct.
20	Correct	6 ms	2908 KB	Correct.
21	Correct	9 ms	3544 KB	Correct.
22	Correct	36 ms	6748 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	236 ms	4504 KB	Correct.
2	Correct	44 ms	5208 KB	Correct.
3	Correct	199 ms	63056 KB	Correct.
4	Correct	233 ms	8900 KB	Correct.
5	Correct	940 ms	76884 KB	Correct.
6	Correct	829 ms	70788 KB	Correct.
7	Correct	459 ms	27260 KB	Correct.
8	Correct	168 ms	5908 KB	Correct.
9	Correct	210 ms	5368 KB	Correct.
10	Correct	213 ms	5400 KB	Correct.
11	Correct	158 ms	3928 KB	Correct.
12	Correct	216 ms	5608 KB	Correct.
13	Correct	236 ms	5432 KB	Correct.
14	Correct	1245 ms	49328 KB	Correct.
15	Correct	672 ms	37140 KB	Correct.
16	Correct	369 ms	16736 KB	Correct.
17	Correct	203 ms	6944 KB	Correct.
18	Correct	230 ms	5460 KB	Correct.
19	Correct	234 ms	5472 KB	Correct.
20	Correct	229 ms	5584 KB	Correct.
21	Correct	495 ms	6280 KB	Correct.
22	Correct	9 ms	2904 KB	Correct.
23	Correct	15 ms	3944 KB	Correct.
24	Correct	75 ms	10796 KB	Correct.

Submission #968387

Compilation message