oj.uz

Submission #750414

# Submission time Handle Problem Language Result Execution time Memory
750414 2023-05-29T13:32:15 Z I_love_Hoang_Yen Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 91084 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, 100);
    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 22 ms 468 KB Correct.
2 Correct 22 ms 460 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 672 KB Correct.
2 Correct 27 ms 700 KB Correct.
3 Correct 25 ms 724 KB Correct.
4 Correct 27 ms 708 KB Correct.
5 Correct 30 ms 684 KB Correct.
6 Correct 28 ms 3840 KB Correct.
7 Correct 32 ms 3780 KB Correct.
8 Correct 15 ms 7512 KB Correct.
9 Correct 28 ms 428 KB Correct.
10 Correct 27 ms 340 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 660 KB Correct.
2 Correct 28 ms 596 KB Correct.
3 Correct 32 ms 716 KB Correct.
4 Correct 32 ms 404 KB Correct.
5 Correct 34 ms 340 KB Correct.
6 Correct 6 ms 3248 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 22340 KB Correct.
2 Correct 164 ms 720 KB Correct.
3 Correct 149 ms 688 KB Correct.
4 Correct 164 ms 812 KB Correct.
5 Correct 135 ms 408 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 704 KB Correct.
2 Correct 28 ms 684 KB Correct.
3 Correct 28 ms 684 KB Correct.
4 Correct 34 ms 3644 KB Correct.
5 Correct 39 ms 424 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 724 KB Correct.
2 Correct 23 ms 696 KB Correct.
3 Correct 53 ms 27900 KB Correct.
4 Correct 20 ms 2468 KB Correct.
5 Correct 28 ms 416 KB Correct.
6 Correct 27 ms 724 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 736 KB Correct.
2 Correct 35 ms 852 KB Correct.
3 Correct 465 ms 27528 KB Correct.
4 Correct 187 ms 7208 KB Correct.
5 Correct 1158 ms 19592 KB Correct.
6 Correct 486 ms 8856 KB Correct.
7 Correct 215 ms 6864 KB Correct.
8 Correct 176 ms 1508 KB Correct.
9 Correct 195 ms 732 KB Correct.
10 Correct 207 ms 716 KB Correct.
11 Correct 193 ms 944 KB Correct.
12 Correct 202 ms 676 KB Correct.
13 Correct 221 ms 788 KB Correct.
14 Correct 217 ms 9004 KB Correct.
15 Correct 209 ms 2496 KB Correct.
16 Correct 205 ms 764 KB Correct.
17 Correct 249 ms 828 KB Correct.
18 Correct 221 ms 660 KB Correct.
19 Correct 580 ms 760 KB Correct.
20 Correct 17 ms 340 KB Correct.
21 Correct 18 ms 588 KB Correct.
22 Correct 40 ms 1076 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1399 ms 1372 KB Correct.
2 Correct 169 ms 1748 KB Correct.
3 Correct 318 ms 91084 KB Correct.
4 Correct 503 ms 4044 KB Correct.
5 Execution timed out 3052 ms 44600 KB Time limit exceeded
6 Halted 0 ms 0 KB -