#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]) {
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 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));
if (n <= 3) {
vector<tuple<int,int,int>> edges(m);
for (int i = 0; i < m; ++i) {
assert(0 <= edge_froms[i] && edge_froms[i] < n);
assert(0 <= edge_tos[i] && edge_tos[i] < n);
assert(1 <= edge_costs[i] && edge_costs[i] < 1000111000);
edges[i] = {
edge_froms[i],
edge_tos[i],
edge_costs[i]
};
}
return sub1(
n, maxDiv2, target,
edges, node_types);
}
int minType = *min_element(node_types.begin(), node_types.end());
int maxType = *max_element(node_types.begin(), node_types.end());
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);
}
if (minType >= 0 && maxType == 1) {
return sub36(n, target, g, node_types);
}
return 0.0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
436 KB |
Correct. |
2 |
Correct |
17 ms |
384 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
468 KB |
Correct. |
2 |
Correct |
33 ms |
448 KB |
Correct. |
3 |
Correct |
30 ms |
460 KB |
Correct. |
4 |
Correct |
32 ms |
340 KB |
Correct. |
5 |
Correct |
32 ms |
460 KB |
Correct. |
6 |
Correct |
25 ms |
1360 KB |
Correct. |
7 |
Correct |
34 ms |
1304 KB |
Correct. |
8 |
Correct |
14 ms |
2388 KB |
Correct. |
9 |
Correct |
30 ms |
340 KB |
Correct. |
10 |
Correct |
28 ms |
384 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
33 ms |
396 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
29 ms |
5324 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
400 KB |
Correct. |
2 |
Correct |
28 ms |
420 KB |
Correct. |
3 |
Correct |
29 ms |
452 KB |
Correct. |
4 |
Correct |
26 ms |
1108 KB |
Correct. |
5 |
Correct |
24 ms |
340 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
29 ms |
420 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
22 ms |
400 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
22 ms |
440 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |