oj.uz

Submission #750026

# Submission time Handle Problem Language Result Execution time Memory
750026 2023-05-29T04:36:49 Z I_love_Hoang_Yen Cyberland (APIO23_cyberland) C++17
97 / 100
 2351 ms 122504 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 sub8(
        int n, int target, int maxDiv2,
        const vector<vector<pair<int,int>>>& g,
        vector<int>& node_types) {
    maxDiv2 = min(maxDiv2, 50);
    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 26 ms 476 KB Correct.
2 Correct 26 ms 364 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 688 KB Correct.
2 Correct 33 ms 688 KB Correct.
3 Correct 31 ms 716 KB Correct.
4 Correct 33 ms 692 KB Correct.
5 Correct 34 ms 740 KB Correct.
6 Correct 31 ms 3856 KB Correct.
7 Correct 39 ms 3812 KB Correct.
8 Correct 18 ms 7508 KB Correct.
9 Correct 32 ms 408 KB Correct.
10 Correct 32 ms 392 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 700 KB Correct.
2 Correct 32 ms 736 KB Correct.
3 Correct 31 ms 724 KB Correct.
4 Correct 35 ms 412 KB Correct.
5 Correct 35 ms 340 KB Correct.
6 Correct 8 ms 3668 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 31008 KB Correct.
2 Correct 331 ms 1308 KB Correct.
3 Correct 284 ms 1328 KB Correct.
4 Correct 304 ms 1168 KB Correct.
5 Correct 263 ms 660 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 684 KB Correct.
2 Correct 33 ms 672 KB Correct.
3 Correct 29 ms 596 KB Correct.
4 Correct 28 ms 3668 KB Correct.
5 Correct 27 ms 340 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 724 KB Correct.
2 Correct 29 ms 596 KB Correct.
3 Correct 55 ms 27852 KB Correct.
4 Correct 21 ms 2684 KB Correct.
5 Correct 31 ms 340 KB Correct.
6 Correct 28 ms 720 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 2104 KB Correct.
2 Correct 51 ms 3212 KB Correct.
3 Correct 1226 ms 31328 KB Correct.
4 Correct 756 ms 8176 KB Correct.
5 Correct 2351 ms 122504 KB Correct.
6 Correct 1152 ms 79848 KB Correct.
7 Correct 707 ms 7912 KB Correct.
8 Correct 669 ms 1756 KB Correct.
9 Correct 314 ms 2692 KB Correct.
10 Correct 321 ms 2252 KB Correct.
11 Correct 665 ms 1180 KB Correct.
12 Correct 330 ms 2252 KB Correct.
13 Correct 362 ms 2352 KB Correct.
14 Correct 687 ms 10148 KB Correct.
15 Correct 669 ms 3516 KB Correct.
16 Correct 330 ms 2252 KB Correct.
17 Correct 397 ms 2000 KB Correct.
18 Correct 390 ms 2064 KB Correct.
19 Correct 917 ms 2076 KB Correct.
20 Correct 27 ms 852 KB Correct.
21 Correct 26 ms 1456 KB Correct.
22 Correct 66 ms 8140 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 756 ms 4484 KB Correct.
2 Correct 110 ms 6888 KB Correct.
3 Incorrect 627 ms 52008 KB Wrong Answer.
4 Halted 0 ms 0 KB -