#include "cyberland.h"
#include <bits/stdc++.h>
#define SZ(s) ((int) ((s).size()))
using namespace std;
const int ZERO = 0;
const int NORMAL = 1;
const int DIV2 = 2;
void upMin(double& res, double val) {
if (res < -0.5) res = val;
else res = min(res, val);
}
// N <= 3
double sub1(
int n, int maxDiv2, int target,
const vector<tuple<int,int,int>>& edges,
const vector<int>& node_types) {
if (target == 0) {
return 0.0;
}
double res = -1;
vector<vector<double>> costs(n, vector<double> (n, -1));
for (auto [u, v, cost] : edges) {
costs[u][v] = costs[v][u] = cost;
}
// go directly from 0 -> target
if (costs[0][target] >= 0)
upMin(res, costs[0][target]);
if (n <= 2) return res;
// go 0 -> other vertex -> target
int other = 3 - target;
if (costs[0][other] >= 0 && costs[other][target] >= 0) {
switch (node_types[other]) {
case NORMAL:
upMin(res, costs[0][other] + costs[other][target]);
break;
case ZERO:
upMin(res, costs[other][target]);
break;
case DIV2:
if (maxDiv2 >= 1) {
upMin(res, costs[0][other] / 2.0 + costs[other][target]);
} else {
upMin(res, costs[0][other] + costs[other][target]);
}
break;
}
}
return res;
}
// All nodes are NORMAL
double sub25(
int n, int target,
const vector<vector<pair<int,int>>>& g) {
const int64_t INF = 1e18;
vector<int64_t> dists(n, INF);
set<pair<int64_t, int>> all;
dists[0] = 0;
all.insert({0LL, 0});
while (!all.empty()) {
auto [dist, u] = *all.begin();
all.erase(all.begin());
if (dist != dists[u]) continue;
for (auto [v, cost] : g[u]) {
int64_t cur = dist + cost;
if (cur < dists[v]) {
dists[v] = cur;
all.insert({cur, v});
}
}
}
if (dists[target] == INF) dists[target] = -1;
return dists[target];
}
// All nodes are NORMAL or ZERO
double sub36(
int n, int target,
const vector<vector<pair<int,int>>>& g,
vector<int>& node_types) {
// BFS to find all reachable ZERO nodes
vector<bool> visited(n, false);
queue<int> qu;
qu.push(0);
visited[0] = true;
while (!qu.empty()) {
int u = qu.front(); qu.pop();
for (auto [v, _] : g[u]) {
if (!visited[v] && v != target) {
visited[v] = true;
qu.push(v);
}
}
}
// Dijkstra from all reachable ZERO nodes
const int64_t INF = 1e18;
vector<int64_t> dists(n, INF);
set<pair<int64_t, int>> all;
node_types[0] = ZERO;
for (int i = 0; i < n; ++i) {
if (visited[i] && node_types[i] == ZERO) {
dists[i] = 0;
all.insert({0LL, i});
}
}
while (!all.empty()) {
auto [dist, u] = *all.begin();
all.erase(all.begin());
if (dist != dists[u]) continue;
for (auto [v, cost] : g[u]) {
int64_t cur = dist + cost;
if (cur < dists[v]) {
dists[v] = cur;
all.insert({cur, v});
}
}
}
if (dists[target] == INF) dists[target] = -1;
return dists[target];
}
double sub47(
int n, int target, int maxDiv2,
const vector<vector<pair<int,int>>>& g,
vector<int>& node_types) {
// BFS to find all reachable ZERO nodes
vector<bool> visited(n, false);
queue<int> qu;
qu.push(0);
visited[0] = true;
while (!qu.empty()) {
int u = qu.front(); qu.pop();
for (auto [v, _] : g[u]) {
if (!visited[v] && v != target) {
visited[v] = true;
qu.push(v);
}
}
}
// SPFA from all reachable ZERO nodes
vector<vector<double>> dists(n, vector<double> (maxDiv2 + 1, 1e18));
set<tuple<double, int, int>> all;
node_types[0] = ZERO;
for (int i = 0; i < n; ++i) {
if (visited[i] && node_types[i] == ZERO) {
dists[i][0] = 0;
all.insert({0.0, i, 0});
}
}
while (!all.empty()) {
auto [dist, u, div2] = *all.begin();
all.erase(all.begin());
if (dist != dists[u][div2]) continue;
if (u == target) continue; // must stop when reaching target node
for (auto [v, cost] : g[u]) {
double cur = dist + cost;
if (cur < dists[v][div2]) {
dists[v][div2] = cur;
all.insert({cur, v, div2});
}
cur /= 2.0;
if (node_types[v] == DIV2 && div2 < maxDiv2 && cur < dists[v][div2+1]) {
dists[v][div2 + 1] = cur;
all.insert({cur, v, div2 + 1});
}
}
}
double res = *min_element(dists[target].begin(), dists[target].end());
if (res > 1e17) res = -1;
return res;
}
double sub8(
int n, int target, int maxDiv2,
const vector<vector<pair<int,int>>>& g,
vector<int>& node_types) {
maxDiv2 = min(maxDiv2, 100);
return sub47(n, target, maxDiv2, g, node_types);
}
double solve(
int n, int m, int maxDiv2, int target,
vector<int> edge_froms,
vector<int> edge_tos,
vector<int> edge_costs,
vector<int> node_types) {
assert(m == SZ(edge_froms));
assert(m == SZ(edge_tos));
assert(m == SZ(edge_costs));
assert(n == SZ(node_types));
vector<vector<pair<int,int>>> g(n);
for (int i = 0; i < m; ++i) {
int u = edge_froms[i];
int v = edge_tos[i];
int cost = edge_costs[i];
g[u].emplace_back(v, cost);
g[v].emplace_back(u, cost);
}
return sub8(n, target, maxDiv2, g, node_types);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
456 KB |
Correct. |
2 |
Correct |
24 ms |
416 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
724 KB |
Correct. |
2 |
Correct |
34 ms |
716 KB |
Correct. |
3 |
Correct |
31 ms |
724 KB |
Correct. |
4 |
Correct |
32 ms |
700 KB |
Correct. |
5 |
Correct |
32 ms |
688 KB |
Correct. |
6 |
Correct |
28 ms |
3904 KB |
Correct. |
7 |
Correct |
38 ms |
3800 KB |
Correct. |
8 |
Correct |
21 ms |
7540 KB |
Correct. |
9 |
Correct |
31 ms |
416 KB |
Correct. |
10 |
Correct |
30 ms |
340 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
716 KB |
Correct. |
2 |
Correct |
31 ms |
680 KB |
Correct. |
3 |
Correct |
30 ms |
728 KB |
Correct. |
4 |
Correct |
33 ms |
424 KB |
Correct. |
5 |
Correct |
34 ms |
424 KB |
Correct. |
6 |
Correct |
7 ms |
3500 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
335 ms |
30968 KB |
Correct. |
2 |
Correct |
330 ms |
1404 KB |
Correct. |
3 |
Correct |
278 ms |
1380 KB |
Correct. |
4 |
Correct |
299 ms |
1288 KB |
Correct. |
5 |
Correct |
264 ms |
568 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
624 KB |
Correct. |
2 |
Correct |
30 ms |
672 KB |
Correct. |
3 |
Correct |
28 ms |
688 KB |
Correct. |
4 |
Correct |
29 ms |
3668 KB |
Correct. |
5 |
Correct |
26 ms |
412 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
724 KB |
Correct. |
2 |
Correct |
25 ms |
680 KB |
Correct. |
3 |
Correct |
50 ms |
27948 KB |
Correct. |
4 |
Correct |
19 ms |
2648 KB |
Correct. |
5 |
Correct |
31 ms |
420 KB |
Correct. |
6 |
Correct |
27 ms |
636 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
377 ms |
2208 KB |
Correct. |
2 |
Correct |
55 ms |
3204 KB |
Correct. |
3 |
Correct |
1176 ms |
31196 KB |
Correct. |
4 |
Correct |
738 ms |
8092 KB |
Correct. |
5 |
Correct |
2318 ms |
122580 KB |
Correct. |
6 |
Correct |
1186 ms |
79832 KB |
Correct. |
7 |
Correct |
735 ms |
7908 KB |
Correct. |
8 |
Correct |
682 ms |
1780 KB |
Correct. |
9 |
Correct |
319 ms |
2832 KB |
Correct. |
10 |
Correct |
332 ms |
2252 KB |
Correct. |
11 |
Correct |
655 ms |
1080 KB |
Correct. |
12 |
Correct |
343 ms |
2288 KB |
Correct. |
13 |
Correct |
381 ms |
2304 KB |
Correct. |
14 |
Correct |
684 ms |
10516 KB |
Correct. |
15 |
Correct |
696 ms |
3556 KB |
Correct. |
16 |
Correct |
333 ms |
2152 KB |
Correct. |
17 |
Correct |
385 ms |
2012 KB |
Correct. |
18 |
Correct |
390 ms |
2016 KB |
Correct. |
19 |
Correct |
913 ms |
2000 KB |
Correct. |
20 |
Correct |
31 ms |
848 KB |
Correct. |
21 |
Correct |
26 ms |
1416 KB |
Correct. |
22 |
Correct |
65 ms |
8228 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1706 ms |
9324 KB |
Correct. |
2 |
Correct |
266 ms |
14424 KB |
Correct. |
3 |
Correct |
1294 ms |
91184 KB |
Correct. |
4 |
Correct |
1688 ms |
8556 KB |
Correct. |
5 |
Execution timed out |
3095 ms |
411400 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |