#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));
queue<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.push({0.0, i, 0});
}
}
while (!all.empty()) {
auto [dist, u, div2] = all.front(); all.pop();
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.push({cur, v, div2});
}
cur /= 2.0;
if (node_types[v] == DIV2 && div2 < maxDiv2 && cur < dists[v][div2+1]) {
dists[v][div2 + 1] = cur;
all.push({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 |
22 ms |
468 KB |
Correct. |
2 |
Correct |
22 ms |
460 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
672 KB |
Correct. |
2 |
Correct |
27 ms |
700 KB |
Correct. |
3 |
Correct |
25 ms |
724 KB |
Correct. |
4 |
Correct |
27 ms |
708 KB |
Correct. |
5 |
Correct |
30 ms |
684 KB |
Correct. |
6 |
Correct |
28 ms |
3840 KB |
Correct. |
7 |
Correct |
32 ms |
3780 KB |
Correct. |
8 |
Correct |
15 ms |
7512 KB |
Correct. |
9 |
Correct |
28 ms |
428 KB |
Correct. |
10 |
Correct |
27 ms |
340 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
660 KB |
Correct. |
2 |
Correct |
28 ms |
596 KB |
Correct. |
3 |
Correct |
32 ms |
716 KB |
Correct. |
4 |
Correct |
32 ms |
404 KB |
Correct. |
5 |
Correct |
34 ms |
340 KB |
Correct. |
6 |
Correct |
6 ms |
3248 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
112 ms |
22340 KB |
Correct. |
2 |
Correct |
164 ms |
720 KB |
Correct. |
3 |
Correct |
149 ms |
688 KB |
Correct. |
4 |
Correct |
164 ms |
812 KB |
Correct. |
5 |
Correct |
135 ms |
408 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
704 KB |
Correct. |
2 |
Correct |
28 ms |
684 KB |
Correct. |
3 |
Correct |
28 ms |
684 KB |
Correct. |
4 |
Correct |
34 ms |
3644 KB |
Correct. |
5 |
Correct |
39 ms |
424 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
724 KB |
Correct. |
2 |
Correct |
23 ms |
696 KB |
Correct. |
3 |
Correct |
53 ms |
27900 KB |
Correct. |
4 |
Correct |
20 ms |
2468 KB |
Correct. |
5 |
Correct |
28 ms |
416 KB |
Correct. |
6 |
Correct |
27 ms |
724 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
250 ms |
736 KB |
Correct. |
2 |
Correct |
35 ms |
852 KB |
Correct. |
3 |
Correct |
465 ms |
27528 KB |
Correct. |
4 |
Correct |
187 ms |
7208 KB |
Correct. |
5 |
Correct |
1158 ms |
19592 KB |
Correct. |
6 |
Correct |
486 ms |
8856 KB |
Correct. |
7 |
Correct |
215 ms |
6864 KB |
Correct. |
8 |
Correct |
176 ms |
1508 KB |
Correct. |
9 |
Correct |
195 ms |
732 KB |
Correct. |
10 |
Correct |
207 ms |
716 KB |
Correct. |
11 |
Correct |
193 ms |
944 KB |
Correct. |
12 |
Correct |
202 ms |
676 KB |
Correct. |
13 |
Correct |
221 ms |
788 KB |
Correct. |
14 |
Correct |
217 ms |
9004 KB |
Correct. |
15 |
Correct |
209 ms |
2496 KB |
Correct. |
16 |
Correct |
205 ms |
764 KB |
Correct. |
17 |
Correct |
249 ms |
828 KB |
Correct. |
18 |
Correct |
221 ms |
660 KB |
Correct. |
19 |
Correct |
580 ms |
760 KB |
Correct. |
20 |
Correct |
17 ms |
340 KB |
Correct. |
21 |
Correct |
18 ms |
588 KB |
Correct. |
22 |
Correct |
40 ms |
1076 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1399 ms |
1372 KB |
Correct. |
2 |
Correct |
169 ms |
1748 KB |
Correct. |
3 |
Correct |
318 ms |
91084 KB |
Correct. |
4 |
Correct |
503 ms |
4044 KB |
Correct. |
5 |
Execution timed out |
3052 ms |
44600 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |