oj.uz

Submission #750025

# Submission time Handle Problem Language Result Execution time Memory
750025 2023-05-29T04:36:03 Z I_love_Hoang_Yen Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 356328 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 24 ms 392 KB Correct.
2 Correct 25 ms 468 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 708 KB Correct.
2 Correct 34 ms 672 KB Correct.
3 Correct 35 ms 672 KB Correct.
4 Correct 32 ms 704 KB Correct.
5 Correct 35 ms 764 KB Correct.
6 Correct 28 ms 3864 KB Correct.
7 Correct 36 ms 3796 KB Correct.
8 Correct 18 ms 7508 KB Correct.
9 Correct 32 ms 340 KB Correct.
10 Correct 30 ms 424 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 712 KB Correct.
2 Correct 33 ms 712 KB Correct.
3 Correct 32 ms 736 KB Correct.
4 Correct 33 ms 416 KB Correct.
5 Correct 35 ms 468 KB Correct.
6 Correct 8 ms 3540 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 30964 KB Correct.
2 Correct 333 ms 1260 KB Correct.
3 Correct 274 ms 1260 KB Correct.
4 Correct 296 ms 1220 KB Correct.
5 Correct 266 ms 604 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 724 KB Correct.
2 Correct 30 ms 636 KB Correct.
3 Correct 29 ms 596 KB Correct.
4 Correct 31 ms 3624 KB Correct.
5 Correct 27 ms 340 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 704 KB Correct.
2 Correct 26 ms 692 KB Correct.
3 Correct 58 ms 27872 KB Correct.
4 Correct 21 ms 2544 KB Correct.
5 Correct 30 ms 416 KB Correct.
6 Correct 28 ms 712 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 2180 KB Correct.
2 Correct 51 ms 3212 KB Correct.
3 Correct 1165 ms 31264 KB Correct.
4 Correct 750 ms 7992 KB Correct.
5 Correct 2361 ms 122328 KB Correct.
6 Correct 1150 ms 79836 KB Correct.
7 Correct 697 ms 7916 KB Correct.
8 Correct 669 ms 1972 KB Correct.
9 Correct 311 ms 2764 KB Correct.
10 Correct 311 ms 2180 KB Correct.
11 Correct 688 ms 1048 KB Correct.
12 Correct 336 ms 2248 KB Correct.
13 Correct 358 ms 2572 KB Correct.
14 Correct 642 ms 10120 KB Correct.
15 Correct 664 ms 3484 KB Correct.
16 Correct 318 ms 2276 KB Correct.
17 Correct 378 ms 2088 KB Correct.
18 Correct 391 ms 2156 KB Correct.
19 Correct 911 ms 2052 KB Correct.
20 Correct 26 ms 840 KB Correct.
21 Correct 26 ms 1416 KB Correct.
22 Correct 58 ms 8188 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1225 ms 7200 KB Correct.
2 Correct 189 ms 10604 KB Correct.
3 Correct 912 ms 67784 KB Correct.
4 Correct 1434 ms 6544 KB Correct.
5 Execution timed out 3076 ms 356328 KB Time limit exceeded
6 Halted 0 ms 0 KB -