oj.uz

Submission #750037

# Submission time Handle Problem Language Result Execution time Memory
750037 2023-05-29T04:56:01 Z I_love_Hoang_Yen Cyberland (APIO23_cyberland) C++17
100 / 100
 612 ms 11240 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);
            }
        }
    }

    // Dijkstra from all reachable ZERO nodes
    vector<double> dists(n, 1e18);
    vector<int> trace(n, -1);
    set<pair<double, int>> all;
    node_types[0] = ZERO;
    for (int i = 0; i < n; ++i) {
        if (visited[i] && node_types[i] == ZERO) {
            dists[i] = 0;
            trace[i] = i;
            all.insert({0.0, i});
        }
    }

    for (int div2 = 0; div2 <= maxDiv2; ++div2) {
        set<int> next_turn;
        vector<double> dist_next_turn(n, 1e18);
        while (!all.empty()) {
            auto [dist, u] = *all.begin();
            all.erase(all.begin());
            if (dist != dists[u]) 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]) {
                    trace[v] = u;
                    dists[v] = cur;
                    all.insert({cur, v});
                }
                cur /= 2.0;
                if (node_types[v] == DIV2 && cur < dist_next_turn[v]) {
                    next_turn.insert(v);
                    dist_next_turn[v] = cur;
                }
            }
        }

        all.clear();
        for (int v : next_turn) {
            dists[v] = dist_next_turn[v];
            all.insert({dists[v], v});
        }
    }
    double res = dists[target];
    return (res > 1e17) ? -1 : 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 27 ms 340 KB Correct.
2 Correct 26 ms 476 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 468 KB Correct.
2 Correct 35 ms 460 KB Correct.
3 Correct 31 ms 468 KB Correct.
4 Correct 35 ms 468 KB Correct.
5 Correct 32 ms 464 KB Correct.
6 Correct 26 ms 1388 KB Correct.
7 Correct 35 ms 1468 KB Correct.
8 Correct 15 ms 2660 KB Correct.
9 Correct 32 ms 392 KB Correct.
10 Correct 31 ms 396 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 472 KB Correct.
2 Correct 33 ms 468 KB Correct.
3 Correct 35 ms 468 KB Correct.
4 Correct 33 ms 340 KB Correct.
5 Correct 36 ms 396 KB Correct.
6 Correct 7 ms 1448 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 7032 KB Correct.
2 Correct 93 ms 484 KB Correct.
3 Correct 78 ms 496 KB Correct.
4 Correct 84 ms 424 KB Correct.
5 Correct 58 ms 384 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 476 KB Correct.
2 Correct 29 ms 468 KB Correct.
3 Correct 30 ms 476 KB Correct.
4 Correct 27 ms 1304 KB Correct.
5 Correct 26 ms 396 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 444 KB Correct.
2 Correct 28 ms 456 KB Correct.
3 Correct 44 ms 8700 KB Correct.
4 Correct 23 ms 1164 KB Correct.
5 Correct 29 ms 388 KB Correct.
6 Correct 29 ms 468 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 448 KB Correct.
2 Correct 12 ms 468 KB Correct.
3 Correct 269 ms 11240 KB Correct.
4 Correct 186 ms 2668 KB Correct.
5 Correct 335 ms 8396 KB Correct.
6 Correct 120 ms 5448 KB Correct.
7 Correct 170 ms 3084 KB Correct.
8 Correct 159 ms 752 KB Correct.
9 Correct 78 ms 468 KB Correct.
10 Correct 71 ms 468 KB Correct.
11 Correct 152 ms 684 KB Correct.
12 Correct 79 ms 440 KB Correct.
13 Correct 77 ms 492 KB Correct.
14 Correct 167 ms 5756 KB Correct.
15 Correct 162 ms 1796 KB Correct.
16 Correct 78 ms 464 KB Correct.
17 Correct 95 ms 500 KB Correct.
18 Correct 86 ms 416 KB Correct.
19 Correct 223 ms 436 KB Correct.
20 Correct 5 ms 340 KB Correct.
21 Correct 6 ms 340 KB Correct.
22 Correct 9 ms 852 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 412 KB Correct.
2 Correct 19 ms 468 KB Correct.
3 Correct 172 ms 10836 KB Correct.
4 Correct 189 ms 984 KB Correct.
5 Correct 612 ms 8420 KB Correct.
6 Correct 230 ms 5452 KB Correct.
7 Correct 231 ms 4636 KB Correct.
8 Correct 188 ms 628 KB Correct.
9 Correct 121 ms 416 KB Correct.
10 Correct 124 ms 440 KB Correct.
11 Correct 275 ms 580 KB Correct.
12 Correct 140 ms 496 KB Correct.
13 Correct 132 ms 436 KB Correct.
14 Correct 406 ms 6516 KB Correct.
15 Correct 490 ms 5880 KB Correct.
16 Correct 277 ms 2324 KB Correct.
17 Correct 202 ms 844 KB Correct.
18 Correct 128 ms 460 KB Correct.
19 Correct 158 ms 712 KB Correct.
20 Correct 147 ms 400 KB Correct.
21 Correct 392 ms 448 KB Correct.
22 Correct 8 ms 340 KB Correct.
23 Correct 15 ms 392 KB Correct.
24 Correct 15 ms 852 KB Correct.