oj.uz

답안 #750028

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
750028 2023-05-29T04:38:16 Z I_love_Hoang_Yen 사이버랜드 (APIO23_cyberland) C++17
97 / 100
 2336 ms 122568 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, 65);
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 468 KB Correct.
2 Correct 26 ms 468 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 724 KB Correct.
2 Correct 35 ms 668 KB Correct.
3 Correct 35 ms 684 KB Correct.
4 Correct 33 ms 712 KB Correct.
5 Correct 34 ms 724 KB Correct.
6 Correct 29 ms 3864 KB Correct.
7 Correct 45 ms 3892 KB Correct.
8 Correct 21 ms 7508 KB Correct.
9 Correct 35 ms 340 KB Correct.
10 Correct 32 ms 416 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 712 KB Correct.
2 Correct 33 ms 732 KB Correct.
3 Correct 31 ms 724 KB Correct.
4 Correct 35 ms 372 KB Correct.
5 Correct 37 ms 408 KB Correct.
6 Correct 8 ms 3500 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 325 ms 30968 KB Correct.
2 Correct 322 ms 1344 KB Correct.
3 Correct 276 ms 1364 KB Correct.
4 Correct 300 ms 1320 KB Correct.
5 Correct 258 ms 552 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 684 KB Correct.
2 Correct 29 ms 676 KB Correct.
3 Correct 29 ms 692 KB Correct.
4 Correct 29 ms 3616 KB Correct.
5 Correct 26 ms 416 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 716 KB Correct.
2 Correct 24 ms 688 KB Correct.
3 Correct 61 ms 27884 KB Correct.
4 Correct 20 ms 2620 KB Correct.
5 Correct 29 ms 412 KB Correct.
6 Correct 27 ms 704 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 355 ms 2312 KB Correct.
2 Correct 52 ms 3276 KB Correct.
3 Correct 1239 ms 31200 KB Correct.
4 Correct 749 ms 8124 KB Correct.
5 Correct 2336 ms 122568 KB Correct.
6 Correct 1174 ms 79860 KB Correct.
7 Correct 692 ms 7900 KB Correct.
8 Correct 666 ms 1900 KB Correct.
9 Correct 313 ms 2764 KB Correct.
10 Correct 312 ms 2176 KB Correct.
11 Correct 658 ms 976 KB Correct.
12 Correct 336 ms 2224 KB Correct.
13 Correct 356 ms 2280 KB Correct.
14 Correct 664 ms 10116 KB Correct.
15 Correct 671 ms 3440 KB Correct.
16 Correct 321 ms 2144 KB Correct.
17 Correct 385 ms 2016 KB Correct.
18 Correct 386 ms 2100 KB Correct.
19 Correct 875 ms 2140 KB Correct.
20 Correct 27 ms 852 KB Correct.
21 Correct 24 ms 1416 KB Correct.
22 Correct 58 ms 8128 KB Correct.

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1150 ms 6600 KB Correct.
2 Correct 179 ms 9748 KB Correct.
3 Incorrect 840 ms 64544 KB Wrong Answer.
4 Halted 0 ms 0 KB -