Submission #756863

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
756863	2023-06-12T10:38:29 Z	DarkMatter	Cyberland (APIO23_cyberland)	C++17	78 / 100	832 ms	18992 KB

cyberland

#define _CRT_SECURE_NO_WARNINGS
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int>pi;
typedef pair<ll, ll>pl;
typedef vector<pi>vpi;
typedef vector<pl>vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<bool> vb;
const long double PI = acos(-1);
const ll oo = 2e18 + 10;
const int MOD = 1e9 + 7;
const ll N = 2e5 + 10;
#define endl '\n'
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define read(v) for (auto& it : v) scanf("%d", &it);
#define readL(v) for (auto& it : v) scanf("%lld", &it);
#define print(v) for (auto it : v) printf("%d ", it); puts("");
#define printL(v) for (auto it : v) printf("%lld ", it); puts("");
#include <vector>
vpl graph[N];
double cost[N], copCost[N], ret = double(oo);
int n, m, k, h;
bool vis[N];
vi vec;
void reset() {
	for (int i = 0; i <= n; i++)
		vis[i] = false, graph[i].clear();
}
void DFS1(int u) {
	vis[u] = true;
	for (auto& v : graph[u]) {
		if (vis[v.first])
			continue;
		DFS1(v.first);
	}
}
void DFS2(int u) {
	vis[u] = true;
	vec.push_back(u);
	for (auto& v : graph[u]) {
		if (v.first == h || vis[v.first])
			continue;
		DFS2(v.first);
	}
}
void Dijkstra() {
	priority_queue<pair<double, int>>pq;
	for (int i = 0; i < n; i++)
		pq.push({ -cost[i],i });
	while (!pq.empty()) {
		pair<double, int>cur = pq.top();
		pq.pop();
		if (cur.second != h && -cur.first == cost[cur.second]) {
			for (auto& it : graph[cur.second]) {
				double sum = cost[cur.second] + it.second;
				if (sum < cost[it.first]) {
					cost[it.first] = sum, pq.push({ -cost[it.first],it.first });
				}
			}
		}
	}
}
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) {
	n = N, m = M, k = min(K, 70), h = H;
	reset();
	for (int i = 0; i < m; i++)
		graph[x[i]].push_back({ y[i],c[i] }), graph[y[i]].push_back({ x[i],c[i] });
	DFS1(0);
	if (!vis[h])
		return -1;
	for (int i = 0; i <= n; i++)
		cost[i] = oo, vis[i] = false;
	vec.clear();
	DFS2(0);
	for (auto& it : vec)
		if (!arr[it] || !it)
			cost[it] = 0;
	ret = double(oo);
	for (int i = 0; i <= k; i++) {
		Dijkstra();
		ret = min(ret, cost[h]), cost[h] = oo;
		for (int j = 0; j < n; j++)
			copCost[j] = cost[j];
		for (int j = 0; j < n; j++) {
			if (arr[j] != 2)
				continue;
			double mn = oo;
			for (auto& it : graph[j]) {
				double sum = copCost[it.first] + it.second;
				mn = min(mn, sum);
			}
			mn /= double(2);
			cost[j] = min(cost[j], mn);
		}
	}
	return ret;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	41 ms	5076 KB	Correct.
2	Correct	42 ms	5180 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	151 ms	5204 KB	Correct.
2	Correct	169 ms	5196 KB	Correct.
3	Correct	149 ms	5204 KB	Correct.
4	Correct	158 ms	5204 KB	Correct.
5	Correct	188 ms	5256 KB	Correct.
6	Correct	194 ms	6584 KB	Correct.
7	Correct	266 ms	6668 KB	Correct.
8	Correct	133 ms	7844 KB	Correct.
9	Correct	105 ms	5076 KB	Correct.
10	Correct	98 ms	5076 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	162 ms	5176 KB	Correct.
2	Correct	156 ms	5160 KB	Correct.
3	Correct	144 ms	5176 KB	Correct.
4	Correct	117 ms	5080 KB	Correct.
5	Correct	106 ms	5076 KB	Correct.
6	Correct	42 ms	6100 KB	Correct.

Subtask #4
0.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	663 ms	13652 KB	Correct.
2	Incorrect	229 ms	5308 KB	Wrong Answer.
3	Halted	0 ms	0 KB	-

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	82 ms	5416 KB	Correct.
2	Correct	85 ms	5396 KB	Correct.
3	Correct	81 ms	5344 KB	Correct.
4	Correct	133 ms	6740 KB	Correct.
5	Correct	51 ms	5076 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	97 ms	5348 KB	Correct.
2	Correct	65 ms	5336 KB	Correct.
3	Correct	46 ms	11596 KB	Correct.
4	Correct	67 ms	6448 KB	Correct.
5	Correct	58 ms	5080 KB	Correct.
6	Correct	76 ms	5364 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	95 ms	5296 KB	Correct.
2	Correct	15 ms	5312 KB	Correct.
3	Correct	832 ms	18992 KB	Correct.
4	Correct	461 ms	8608 KB	Correct.
5	Correct	351 ms	14728 KB	Correct.
6	Correct	120 ms	11848 KB	Correct.
7	Correct	413 ms	8560 KB	Correct.
8	Correct	320 ms	5680 KB	Correct.
9	Correct	76 ms	5272 KB	Correct.
10	Correct	76 ms	5324 KB	Correct.
11	Correct	286 ms	5524 KB	Correct.
12	Correct	100 ms	5324 KB	Correct.
13	Correct	85 ms	5372 KB	Correct.
14	Correct	406 ms	12276 KB	Correct.
15	Correct	359 ms	7036 KB	Correct.
16	Correct	85 ms	5364 KB	Correct.
17	Correct	109 ms	5324 KB	Correct.
18	Correct	91 ms	5324 KB	Correct.
19	Correct	296 ms	5368 KB	Correct.
20	Correct	8 ms	4948 KB	Correct.
21	Correct	8 ms	5076 KB	Correct.
22	Correct	11 ms	5744 KB	Correct.

Subtask #8
0.0 / 3.0

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

Submission #756863

Compilation message