oj.uz

Submission #750022

# Submission time Handle Problem Language Result Execution time Memory
750022 2023-05-29T04:33:51 Z I_love_Hoang_Yen Cyberland (APIO23_cyberland) C++17
97 / 100
 2329 ms 2097156 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);
            }
        }
    }

    // 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 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 sub47(n, target, maxDiv2, g, node_types);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 468 KB Correct.
2 Correct 25 ms 472 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 700 KB Correct.
2 Correct 35 ms 724 KB Correct.
3 Correct 33 ms 768 KB Correct.
4 Correct 35 ms 704 KB Correct.
5 Correct 33 ms 696 KB Correct.
6 Correct 29 ms 3872 KB Correct.
7 Correct 38 ms 3888 KB Correct.
8 Correct 20 ms 7508 KB Correct.
9 Correct 34 ms 340 KB Correct.
10 Correct 36 ms 404 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 712 KB Correct.
2 Correct 34 ms 720 KB Correct.
3 Correct 33 ms 752 KB Correct.
4 Correct 36 ms 416 KB Correct.
5 Correct 35 ms 340 KB Correct.
6 Correct 8 ms 3540 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 30976 KB Correct.
2 Correct 341 ms 1220 KB Correct.
3 Correct 285 ms 1308 KB Correct.
4 Correct 297 ms 1344 KB Correct.
5 Correct 270 ms 468 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 684 KB Correct.
2 Correct 30 ms 596 KB Correct.
3 Correct 30 ms 684 KB Correct.
4 Correct 30 ms 3608 KB Correct.
5 Correct 27 ms 340 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 700 KB Correct.
2 Correct 26 ms 712 KB Correct.
3 Correct 57 ms 27900 KB Correct.
4 Correct 22 ms 2632 KB Correct.
5 Correct 30 ms 416 KB Correct.
6 Correct 33 ms 716 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 2208 KB Correct.
2 Correct 55 ms 3264 KB Correct.
3 Correct 1207 ms 31216 KB Correct.
4 Correct 769 ms 7952 KB Correct.
5 Correct 2329 ms 122592 KB Correct.
6 Correct 1143 ms 79812 KB Correct.
7 Correct 699 ms 8032 KB Correct.
8 Correct 660 ms 2020 KB Correct.
9 Correct 326 ms 2704 KB Correct.
10 Correct 316 ms 2392 KB Correct.
11 Correct 651 ms 1256 KB Correct.
12 Correct 332 ms 2288 KB Correct.
13 Correct 361 ms 2360 KB Correct.
14 Correct 661 ms 10212 KB Correct.
15 Correct 673 ms 3532 KB Correct.
16 Correct 332 ms 2140 KB Correct.
17 Correct 396 ms 2124 KB Correct.
18 Correct 397 ms 2152 KB Correct.
19 Correct 903 ms 2052 KB Correct.
20 Correct 30 ms 840 KB Correct.
21 Correct 26 ms 1424 KB Correct.
22 Correct 58 ms 8192 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 1372 ms 2097156 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -