Submission #750413

#	Time	Username	Problem	Language	Result	Execution time	Memory
750413		I_love_Hoang_Yen	Cyberland (APIO23_cyberland)	C++17	97 / 100	1160 ms	59764 KiB

cyberland

#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, 60);
    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 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 29 / 29
• Subtask 8: 0 / 3