oj.uz

답안 #750021

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
750021 2023-05-29T04:29:30 Z I_love_Hoang_Yen 사이버랜드 (APIO23_cyberland) C++17
49 / 100
 798 ms 2097152 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
    const double INF = 1e18;
    vector<vector<double>> dists(n, vector<double> (maxDiv2 + 1, INF));
    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) {
            return dist;
        }

        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});
            }
        }
    }
    return -1.0;
}

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 sub47(n, target, maxDiv2, g, node_types);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 724 KB Correct.
2 Correct 30 ms 708 KB Correct.
3 Correct 28 ms 680 KB Correct.
4 Correct 31 ms 596 KB Correct.
5 Correct 30 ms 716 KB Correct.
6 Correct 24 ms 3880 KB Correct.
7 Correct 32 ms 3796 KB Correct.
8 Correct 18 ms 7508 KB Correct.
9 Correct 29 ms 416 KB Correct.
10 Correct 29 ms 392 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 708 KB Correct.
2 Correct 33 ms 724 KB Correct.
3 Correct 31 ms 700 KB Correct.
4 Correct 33 ms 420 KB Correct.
5 Correct 34 ms 416 KB Correct.
6 Correct 7 ms 3452 KB Correct.

Subtask #4
0.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 256 ms 30920 KB Correct.
2 Incorrect 202 ms 1208 KB Wrong Answer.
3 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 724 KB Correct.
2 Correct 30 ms 596 KB Correct.
3 Correct 32 ms 680 KB Correct.
4 Correct 27 ms 3720 KB Correct.
5 Correct 28 ms 420 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 724 KB Correct.
2 Correct 25 ms 700 KB Correct.
3 Correct 54 ms 27896 KB Correct.
4 Correct 21 ms 2628 KB Correct.
5 Correct 31 ms 340 KB Correct.
6 Correct 28 ms 636 KB Correct.

Subtask #7
0.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 272 ms 2240 KB Correct.
2 Correct 29 ms 3304 KB Correct.
3 Incorrect 69 ms 26220 KB Wrong Answer.
4 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 798 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -