Submission #756864

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
756864	2023-06-12T10:40:54 Z	DarkMatter	Cyberland (APIO23_cyberland)	C++17	78 / 100	1189 ms	24048 KB

cyberland

#include "cyberland.h"

/* 	* In the name of GOD  */

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef long double ld;
#define F first
#define S second
#define mk make_pair
const ll N = 2e5 + 10, INF = 2e18 + 10;
vector <pair <int, ll>> g[N];
ld dis[N], od[N], x[N];
int n, h;
bool vis[N];
vector <int> ww;

void dijkstra() {
	priority_queue <pair <ld, int>> q;
	for (int s = 0; s < n; s++)
		q.push(make_pair((ld)-1.0 * dis[s], s));
	while (!q.empty()) {
		pair <ld, int> p = (q.top());
		int x = p.S;
		q.pop();
		if (dis[x] != -1 * p.F || x == h)
			continue;
		ld d = dis[x];
		for (auto [y, w] : g[x]) {
			if (dis[y] <= d + w) {
				continue;
			}
			dis[y] = d + w;
			q.push(make_pair(-1 * dis[y], y));
		}
	}
}

void dfs(int v) {
	vis[v] = true;
	for (auto [u, w] : g[v]) {
		if (!vis[u])
			dfs(u);
	}
}

void dfs2(int v) {
	vis[v] = true;
	ww.push_back(v);
	for (auto [u, w] : g[v]) {
		if (!vis[u] && u != h)
			dfs2(u);
	}
}

double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
	K = min(K, 70);
	n = N;
	h = H;
	for (int i = 0; i <= n; i++)
		g[i].clear(), vis[i] = false;
	for (int i = 0; i < M; i++) {
		g[x[i]].push_back(mk(y[i], c[i]));
		g[y[i]].push_back(mk(x[i], c[i]));
	}
	dfs(0);
	if (!vis[H]) {
		for (int i = 0; i <= n; i++)
			g[i].clear(), vis[i] = false;
		return -1;
	}
	for (int i = 0; i < n; i++) {
		dis[i] = INF;
	}
	for (int i = 0; i <= n; i++)
		vis[i] = false;
	ww.clear();
	dfs2(0);
	for (int i : ww) {
		if (i == 0 || arr[i] == 0)
			dis[i] = 0;
	}
	ld mn = INF;
	for (int i = 0; i <= K; i++) {
		dijkstra();
		mn = min(mn, dis[H]);
		dis[H] = INF;
		for (int i = 0; i < n; i++)
			od[i] = dis[i];
		for (int i = 0; i < n; i++) {
			if (arr[i] == 2) {
				ld mnn = INF;
				for (auto [j, w] : g[i]) {
					mnn = min(mnn, od[j] + w);
				}
				dis[i] = min(dis[i], (mnn) / (ld)2);
			}
		}
	}
	for (int i = 0; i <= n; i++)
		g[i].clear(), vis[i] = false;
	return mn;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	59 ms	5136 KB	Correct.
2	Correct	68 ms	5072 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	236 ms	5344 KB	Correct.
2	Correct	262 ms	5364 KB	Correct.
3	Correct	253 ms	5372 KB	Correct.
4	Correct	282 ms	5404 KB	Correct.
5	Correct	265 ms	5448 KB	Correct.
6	Correct	364 ms	7148 KB	Correct.
7	Correct	439 ms	7124 KB	Correct.
8	Correct	201 ms	8988 KB	Correct.
9	Correct	182 ms	5100 KB	Correct.
10	Correct	169 ms	5208 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	265 ms	5272 KB	Correct.
2	Correct	258 ms	5272 KB	Correct.
3	Correct	234 ms	5384 KB	Correct.
4	Correct	217 ms	5092 KB	Correct.
5	Correct	191 ms	5076 KB	Correct.
6	Correct	76 ms	6484 KB	Correct.

Subtask #4
0.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1040 ms	16436 KB	Correct.
2	Incorrect	377 ms	5292 KB	Wrong Answer.
3	Halted	0 ms	0 KB	-

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	133 ms	5396 KB	Correct.
2	Correct	136 ms	5376 KB	Correct.
3	Correct	146 ms	5412 KB	Correct.
4	Correct	210 ms	7200 KB	Correct.
5	Correct	82 ms	5092 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	149 ms	5344 KB	Correct.
2	Correct	94 ms	5324 KB	Correct.
3	Correct	48 ms	11484 KB	Correct.
4	Correct	103 ms	6828 KB	Correct.
5	Correct	95 ms	5196 KB	Correct.
6	Correct	129 ms	5400 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	153 ms	5376 KB	Correct.
2	Correct	21 ms	5396 KB	Correct.
3	Correct	1189 ms	24048 KB	Correct.
4	Correct	799 ms	9788 KB	Correct.
5	Correct	601 ms	16848 KB	Correct.
6	Correct	177 ms	12484 KB	Correct.
7	Correct	724 ms	9828 KB	Correct.
8	Correct	474 ms	6020 KB	Correct.
9	Correct	121 ms	5348 KB	Correct.
10	Correct	133 ms	5444 KB	Correct.
11	Correct	427 ms	5472 KB	Correct.
12	Correct	154 ms	5404 KB	Correct.
13	Correct	132 ms	5416 KB	Correct.
14	Correct	542 ms	14928 KB	Correct.
15	Correct	531 ms	7752 KB	Correct.
16	Correct	123 ms	5432 KB	Correct.
17	Correct	172 ms	5524 KB	Correct.
18	Correct	143 ms	5388 KB	Correct.
19	Correct	426 ms	5380 KB	Correct.
20	Correct	11 ms	5076 KB	Correct.
21	Correct	12 ms	5204 KB	Correct.
22	Correct	14 ms	5876 KB	Correct.

Subtask #8
0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	299 ms	5368 KB	Wrong Answer.
2	Halted	0 ms	0 KB	-

Submission #756864

Compilation message