oj.uz

답안 #750024

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

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 456 KB Correct.
2 Correct 24 ms 416 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 724 KB Correct.
2 Correct 34 ms 716 KB Correct.
3 Correct 31 ms 724 KB Correct.
4 Correct 32 ms 700 KB Correct.
5 Correct 32 ms 688 KB Correct.
6 Correct 28 ms 3904 KB Correct.
7 Correct 38 ms 3800 KB Correct.
8 Correct 21 ms 7540 KB Correct.
9 Correct 31 ms 416 KB Correct.
10 Correct 30 ms 340 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 716 KB Correct.
2 Correct 31 ms 680 KB Correct.
3 Correct 30 ms 728 KB Correct.
4 Correct 33 ms 424 KB Correct.
5 Correct 34 ms 424 KB Correct.
6 Correct 7 ms 3500 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 335 ms 30968 KB Correct.
2 Correct 330 ms 1404 KB Correct.
3 Correct 278 ms 1380 KB Correct.
4 Correct 299 ms 1288 KB Correct.
5 Correct 264 ms 568 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 624 KB Correct.
2 Correct 30 ms 672 KB Correct.
3 Correct 28 ms 688 KB Correct.
4 Correct 29 ms 3668 KB Correct.
5 Correct 26 ms 412 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 724 KB Correct.
2 Correct 25 ms 680 KB Correct.
3 Correct 50 ms 27948 KB Correct.
4 Correct 19 ms 2648 KB Correct.
5 Correct 31 ms 420 KB Correct.
6 Correct 27 ms 636 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 377 ms 2208 KB Correct.
2 Correct 55 ms 3204 KB Correct.
3 Correct 1176 ms 31196 KB Correct.
4 Correct 738 ms 8092 KB Correct.
5 Correct 2318 ms 122580 KB Correct.
6 Correct 1186 ms 79832 KB Correct.
7 Correct 735 ms 7908 KB Correct.
8 Correct 682 ms 1780 KB Correct.
9 Correct 319 ms 2832 KB Correct.
10 Correct 332 ms 2252 KB Correct.
11 Correct 655 ms 1080 KB Correct.
12 Correct 343 ms 2288 KB Correct.
13 Correct 381 ms 2304 KB Correct.
14 Correct 684 ms 10516 KB Correct.
15 Correct 696 ms 3556 KB Correct.
16 Correct 333 ms 2152 KB Correct.
17 Correct 385 ms 2012 KB Correct.
18 Correct 390 ms 2016 KB Correct.
19 Correct 913 ms 2000 KB Correct.
20 Correct 31 ms 848 KB Correct.
21 Correct 26 ms 1416 KB Correct.
22 Correct 65 ms 8228 KB Correct.

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1706 ms 9324 KB Correct.
2 Correct 266 ms 14424 KB Correct.
3 Correct 1294 ms 91184 KB Correct.
4 Correct 1688 ms 8556 KB Correct.
5 Execution timed out 3095 ms 411400 KB Time limit exceeded
6 Halted 0 ms 0 KB -