oj.uz

Submission #750463

# Submission time Handle Problem Language Result Execution time Memory
750463 2023-05-29T14:25:26 Z cig32 Cyberland (APIO23_cyberland) C++17
100 / 100
 606 ms 11192 KB 
#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);
            }
        }
    }
 
    // Dijkstra from all reachable ZERO nodes
    vector<double> dists(n, 1e18);
    vector<int> trace(n, -1);
    set<pair<double, int>> all;
    node_types[0] = ZERO;
    for (int i = 0; i < n; ++i) {
        if (visited[i] && node_types[i] == ZERO) {
            dists[i] = 0;
            trace[i] = i;
            all.insert({0.0, i});
        }
    }
 
    for (int div2 = 0; div2 <= maxDiv2; ++div2) {
        set<int> next_turn;
        vector<double> dist_next_turn(n, 1e18);
        while (!all.empty()) {
            auto [dist, u] = *all.begin();
            all.erase(all.begin());
            if (dist != dists[u]) 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]) {
                    trace[v] = u;
                    dists[v] = cur;
                    all.insert({cur, v});
                }
                cur /= 2.0;
                if (node_types[v] == DIV2 && cur < dist_next_turn[v]) {
                    next_turn.insert(v);
                    dist_next_turn[v] = cur;
                }
            }
        }
 
        all.clear();
        for (int v : next_turn) {
            dists[v] = dist_next_turn[v];
            all.insert({dists[v], v});
        }
    }
    double res = dists[target];
    return (res > 1e17) ? -1 : res;
}
 
double sub8(
        int n, int target, int maxDiv2,
        const vector<vector<pair<int,int>>>& g,
        vector<int>& node_types) {
    maxDiv2 = min(maxDiv2, 70);
    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);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 468 KB Correct.
2 Correct 31 ms 424 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 452 KB Correct.
2 Correct 40 ms 460 KB Correct.
3 Correct 37 ms 472 KB Correct.
4 Correct 40 ms 468 KB Correct.
5 Correct 33 ms 468 KB Correct.
6 Correct 29 ms 1476 KB Correct.
7 Correct 34 ms 1484 KB Correct.
8 Correct 16 ms 2644 KB Correct.
9 Correct 47 ms 392 KB Correct.
10 Correct 36 ms 392 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 468 KB Correct.
2 Correct 36 ms 488 KB Correct.
3 Correct 34 ms 488 KB Correct.
4 Correct 35 ms 340 KB Correct.
5 Correct 35 ms 392 KB Correct.
6 Correct 7 ms 1452 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 6984 KB Correct.
2 Correct 90 ms 476 KB Correct.
3 Correct 78 ms 468 KB Correct.
4 Correct 87 ms 436 KB Correct.
5 Correct 59 ms 392 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 464 KB Correct.
2 Correct 33 ms 444 KB Correct.
3 Correct 31 ms 468 KB Correct.
4 Correct 27 ms 1312 KB Correct.
5 Correct 26 ms 396 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 448 KB Correct.
2 Correct 27 ms 492 KB Correct.
3 Correct 50 ms 8700 KB Correct.
4 Correct 18 ms 1172 KB Correct.
5 Correct 30 ms 388 KB Correct.
6 Correct 29 ms 468 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 444 KB Correct.
2 Correct 13 ms 468 KB Correct.
3 Correct 263 ms 11192 KB Correct.
4 Correct 193 ms 2668 KB Correct.
5 Correct 329 ms 8416 KB Correct.
6 Correct 121 ms 5432 KB Correct.
7 Correct 179 ms 2948 KB Correct.
8 Correct 164 ms 716 KB Correct.
9 Correct 72 ms 436 KB Correct.
10 Correct 73 ms 600 KB Correct.
11 Correct 156 ms 588 KB Correct.
12 Correct 79 ms 436 KB Correct.
13 Correct 80 ms 508 KB Correct.
14 Correct 158 ms 5680 KB Correct.
15 Correct 163 ms 1700 KB Correct.
16 Correct 80 ms 412 KB Correct.
17 Correct 89 ms 472 KB Correct.
18 Correct 86 ms 480 KB Correct.
19 Correct 226 ms 432 KB Correct.
20 Correct 6 ms 352 KB Correct.
21 Correct 7 ms 340 KB Correct.
22 Correct 9 ms 852 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 488 KB Correct.
2 Correct 21 ms 468 KB Correct.
3 Correct 168 ms 10936 KB Correct.
4 Correct 191 ms 988 KB Correct.
5 Correct 606 ms 8420 KB Correct.
6 Correct 223 ms 5532 KB Correct.
7 Correct 224 ms 4608 KB Correct.
8 Correct 187 ms 732 KB Correct.
9 Correct 124 ms 432 KB Correct.
10 Correct 132 ms 464 KB Correct.
11 Correct 268 ms 564 KB Correct.
12 Correct 135 ms 500 KB Correct.
13 Correct 135 ms 420 KB Correct.
14 Correct 395 ms 6528 KB Correct.
15 Correct 499 ms 5864 KB Correct.
16 Correct 284 ms 2316 KB Correct.
17 Correct 201 ms 792 KB Correct.
18 Correct 127 ms 448 KB Correct.
19 Correct 153 ms 508 KB Correct.
20 Correct 147 ms 564 KB Correct.
21 Correct 394 ms 340 KB Correct.
22 Correct 8 ms 340 KB Correct.
23 Correct 11 ms 400 KB Correct.
24 Correct 16 ms 852 KB Correct.