oj.uz

Submission #750413

# Submission time Handle Problem Language Result Execution time Memory
750413 2023-05-29T13:31:41 Z I_love_Hoang_Yen Cyberland (APIO23_cyberland) C++17
97 / 100
 1160 ms 59764 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));
    queue<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.push({0.0, i, 0});
        }
    }
    while (!all.empty()) {
        auto [dist, u, div2] = all.front(); all.pop();
        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.push({cur, v, div2});
            }
            cur /= 2.0;
            if (node_types[v] == DIV2 && div2 < maxDiv2 && cur < dists[v][div2+1]) {
                dists[v][div2 + 1] = cur;
                all.push({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, 60);
    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 23 ms 460 KB Correct.
2 Correct 23 ms 400 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 708 KB Correct.
2 Correct 27 ms 672 KB Correct.
3 Correct 25 ms 644 KB Correct.
4 Correct 27 ms 596 KB Correct.
5 Correct 32 ms 728 KB Correct.
6 Correct 26 ms 3824 KB Correct.
7 Correct 31 ms 3848 KB Correct.
8 Correct 16 ms 7520 KB Correct.
9 Correct 26 ms 340 KB Correct.
10 Correct 28 ms 432 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 688 KB Correct.
2 Correct 27 ms 664 KB Correct.
3 Correct 25 ms 724 KB Correct.
4 Correct 28 ms 420 KB Correct.
5 Correct 27 ms 340 KB Correct.
6 Correct 6 ms 3284 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 22276 KB Correct.
2 Correct 168 ms 728 KB Correct.
3 Correct 141 ms 796 KB Correct.
4 Correct 158 ms 744 KB Correct.
5 Correct 135 ms 420 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 700 KB Correct.
2 Correct 27 ms 656 KB Correct.
3 Correct 27 ms 676 KB Correct.
4 Correct 28 ms 3668 KB Correct.
5 Correct 26 ms 340 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 696 KB Correct.
2 Correct 23 ms 596 KB Correct.
3 Correct 62 ms 27900 KB Correct.
4 Correct 20 ms 2468 KB Correct.
5 Correct 29 ms 412 KB Correct.
6 Correct 27 ms 624 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 736 KB Correct.
2 Correct 36 ms 852 KB Correct.
3 Correct 485 ms 27668 KB Correct.
4 Correct 178 ms 7064 KB Correct.
5 Correct 1160 ms 19676 KB Correct.
6 Correct 500 ms 8756 KB Correct.
7 Correct 194 ms 6884 KB Correct.
8 Correct 174 ms 1508 KB Correct.
9 Correct 196 ms 848 KB Correct.
10 Correct 189 ms 700 KB Correct.
11 Correct 182 ms 908 KB Correct.
12 Correct 215 ms 724 KB Correct.
13 Correct 220 ms 768 KB Correct.
14 Correct 230 ms 8996 KB Correct.
15 Correct 210 ms 2492 KB Correct.
16 Correct 204 ms 904 KB Correct.
17 Correct 275 ms 744 KB Correct.
18 Correct 222 ms 680 KB Correct.
19 Correct 597 ms 768 KB Correct.
20 Correct 16 ms 340 KB Correct.
21 Correct 16 ms 596 KB Correct.
22 Correct 39 ms 1112 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 731 ms 996 KB Correct.
2 Correct 102 ms 1236 KB Correct.
3 Incorrect 225 ms 59764 KB Wrong Answer.
4 Halted 0 ms 0 KB -