oj.uz

Submission #750029

# Submission time Handle Problem Language Result Execution time Memory
750029 2023-05-29T04:38:56 Z I_love_Hoang_Yen Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 352204 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, 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 25 ms 396 KB Correct.
2 Correct 25 ms 464 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 684 KB Correct.
2 Correct 43 ms 640 KB Correct.
3 Correct 41 ms 684 KB Correct.
4 Correct 36 ms 700 KB Correct.
5 Correct 34 ms 676 KB Correct.
6 Correct 31 ms 3868 KB Correct.
7 Correct 38 ms 3868 KB Correct.
8 Correct 18 ms 7512 KB Correct.
9 Correct 32 ms 428 KB Correct.
10 Correct 31 ms 436 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 688 KB Correct.
2 Correct 33 ms 684 KB Correct.
3 Correct 32 ms 756 KB Correct.
4 Correct 34 ms 340 KB Correct.
5 Correct 34 ms 420 KB Correct.
6 Correct 8 ms 3540 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 30968 KB Correct.
2 Correct 350 ms 1344 KB Correct.
3 Correct 279 ms 1268 KB Correct.
4 Correct 325 ms 1324 KB Correct.
5 Correct 274 ms 480 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 724 KB Correct.
2 Correct 43 ms 596 KB Correct.
3 Correct 32 ms 676 KB Correct.
4 Correct 30 ms 3620 KB Correct.
5 Correct 26 ms 340 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 720 KB Correct.
2 Correct 25 ms 688 KB Correct.
3 Correct 58 ms 27876 KB Correct.
4 Correct 23 ms 2576 KB Correct.
5 Correct 31 ms 420 KB Correct.
6 Correct 28 ms 712 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 2132 KB Correct.
2 Correct 52 ms 3264 KB Correct.
3 Correct 1290 ms 31240 KB Correct.
4 Correct 808 ms 7952 KB Correct.
5 Correct 2528 ms 122440 KB Correct.
6 Correct 1174 ms 79772 KB Correct.
7 Correct 714 ms 7912 KB Correct.
8 Correct 690 ms 1776 KB Correct.
9 Correct 336 ms 2760 KB Correct.
10 Correct 324 ms 2184 KB Correct.
11 Correct 660 ms 1056 KB Correct.
12 Correct 344 ms 2288 KB Correct.
13 Correct 376 ms 2312 KB Correct.
14 Correct 665 ms 10236 KB Correct.
15 Correct 671 ms 3532 KB Correct.
16 Correct 335 ms 2184 KB Correct.
17 Correct 382 ms 2028 KB Correct.
18 Correct 388 ms 2044 KB Correct.
19 Correct 938 ms 2280 KB Correct.
20 Correct 33 ms 856 KB Correct.
21 Correct 32 ms 1408 KB Correct.
22 Correct 66 ms 8148 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1252 ms 7328 KB Correct.
2 Correct 212 ms 10716 KB Correct.
3 Correct 926 ms 67680 KB Correct.
4 Correct 1456 ms 6412 KB Correct.
5 Execution timed out 3088 ms 352204 KB Time limit exceeded
6 Halted 0 ms 0 KB -