#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, 65);
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 |
25 ms |
468 KB |
Correct. |
2 |
Correct |
26 ms |
468 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
724 KB |
Correct. |
2 |
Correct |
35 ms |
668 KB |
Correct. |
3 |
Correct |
35 ms |
684 KB |
Correct. |
4 |
Correct |
33 ms |
712 KB |
Correct. |
5 |
Correct |
34 ms |
724 KB |
Correct. |
6 |
Correct |
29 ms |
3864 KB |
Correct. |
7 |
Correct |
45 ms |
3892 KB |
Correct. |
8 |
Correct |
21 ms |
7508 KB |
Correct. |
9 |
Correct |
35 ms |
340 KB |
Correct. |
10 |
Correct |
32 ms |
416 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
712 KB |
Correct. |
2 |
Correct |
33 ms |
732 KB |
Correct. |
3 |
Correct |
31 ms |
724 KB |
Correct. |
4 |
Correct |
35 ms |
372 KB |
Correct. |
5 |
Correct |
37 ms |
408 KB |
Correct. |
6 |
Correct |
8 ms |
3500 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
325 ms |
30968 KB |
Correct. |
2 |
Correct |
322 ms |
1344 KB |
Correct. |
3 |
Correct |
276 ms |
1364 KB |
Correct. |
4 |
Correct |
300 ms |
1320 KB |
Correct. |
5 |
Correct |
258 ms |
552 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
684 KB |
Correct. |
2 |
Correct |
29 ms |
676 KB |
Correct. |
3 |
Correct |
29 ms |
692 KB |
Correct. |
4 |
Correct |
29 ms |
3616 KB |
Correct. |
5 |
Correct |
26 ms |
416 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
716 KB |
Correct. |
2 |
Correct |
24 ms |
688 KB |
Correct. |
3 |
Correct |
61 ms |
27884 KB |
Correct. |
4 |
Correct |
20 ms |
2620 KB |
Correct. |
5 |
Correct |
29 ms |
412 KB |
Correct. |
6 |
Correct |
27 ms |
704 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
355 ms |
2312 KB |
Correct. |
2 |
Correct |
52 ms |
3276 KB |
Correct. |
3 |
Correct |
1239 ms |
31200 KB |
Correct. |
4 |
Correct |
749 ms |
8124 KB |
Correct. |
5 |
Correct |
2336 ms |
122568 KB |
Correct. |
6 |
Correct |
1174 ms |
79860 KB |
Correct. |
7 |
Correct |
692 ms |
7900 KB |
Correct. |
8 |
Correct |
666 ms |
1900 KB |
Correct. |
9 |
Correct |
313 ms |
2764 KB |
Correct. |
10 |
Correct |
312 ms |
2176 KB |
Correct. |
11 |
Correct |
658 ms |
976 KB |
Correct. |
12 |
Correct |
336 ms |
2224 KB |
Correct. |
13 |
Correct |
356 ms |
2280 KB |
Correct. |
14 |
Correct |
664 ms |
10116 KB |
Correct. |
15 |
Correct |
671 ms |
3440 KB |
Correct. |
16 |
Correct |
321 ms |
2144 KB |
Correct. |
17 |
Correct |
385 ms |
2016 KB |
Correct. |
18 |
Correct |
386 ms |
2100 KB |
Correct. |
19 |
Correct |
875 ms |
2140 KB |
Correct. |
20 |
Correct |
27 ms |
852 KB |
Correct. |
21 |
Correct |
24 ms |
1416 KB |
Correct. |
22 |
Correct |
58 ms |
8128 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1150 ms |
6600 KB |
Correct. |
2 |
Correct |
179 ms |
9748 KB |
Correct. |
3 |
Incorrect |
840 ms |
64544 KB |
Wrong Answer. |
4 |
Halted |
0 ms |
0 KB |
- |