oj.uz

Submission #750417

# Submission time Handle Problem Language Result Execution time Memory
750417 2023-05-29T13:33:18 Z I_love_Hoang_Yen Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 67532 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));
    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, 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 22 ms 412 KB Correct.
2 Correct 24 ms 424 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 692 KB Correct.
2 Correct 27 ms 664 KB Correct.
3 Correct 28 ms 724 KB Correct.
4 Correct 29 ms 696 KB Correct.
5 Correct 26 ms 724 KB Correct.
6 Correct 22 ms 3856 KB Correct.
7 Correct 29 ms 3828 KB Correct.
8 Correct 15 ms 7516 KB Correct.
9 Correct 28 ms 424 KB Correct.
10 Correct 27 ms 340 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 596 KB Correct.
2 Correct 26 ms 668 KB Correct.
3 Correct 26 ms 744 KB Correct.
4 Correct 31 ms 408 KB Correct.
5 Correct 29 ms 432 KB Correct.
6 Correct 7 ms 3284 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 22296 KB Correct.
2 Correct 154 ms 660 KB Correct.
3 Correct 145 ms 816 KB Correct.
4 Correct 152 ms 688 KB Correct.
5 Correct 132 ms 404 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 680 KB Correct.
2 Correct 29 ms 688 KB Correct.
3 Correct 27 ms 596 KB Correct.
4 Correct 26 ms 3668 KB Correct.
5 Correct 25 ms 340 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 708 KB Correct.
2 Correct 26 ms 692 KB Correct.
3 Correct 56 ms 27904 KB Correct.
4 Correct 18 ms 2396 KB Correct.
5 Correct 27 ms 420 KB Correct.
6 Correct 27 ms 596 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 744 KB Correct.
2 Correct 34 ms 852 KB Correct.
3 Correct 443 ms 27400 KB Correct.
4 Correct 166 ms 7164 KB Correct.
5 Correct 994 ms 19592 KB Correct.
6 Correct 459 ms 8856 KB Correct.
7 Correct 169 ms 6840 KB Correct.
8 Correct 164 ms 1496 KB Correct.
9 Correct 191 ms 772 KB Correct.
10 Correct 202 ms 648 KB Correct.
11 Correct 190 ms 792 KB Correct.
12 Correct 206 ms 712 KB Correct.
13 Correct 208 ms 776 KB Correct.
14 Correct 215 ms 9008 KB Correct.
15 Correct 204 ms 2560 KB Correct.
16 Correct 199 ms 736 KB Correct.
17 Correct 236 ms 740 KB Correct.
18 Correct 219 ms 704 KB Correct.
19 Correct 577 ms 748 KB Correct.
20 Correct 16 ms 340 KB Correct.
21 Correct 15 ms 592 KB Correct.
22 Correct 37 ms 1084 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 892 ms 1164 KB Correct.
2 Correct 119 ms 1364 KB Correct.
3 Correct 240 ms 67532 KB Correct.
4 Correct 323 ms 3048 KB Correct.
5 Execution timed out 3096 ms 34808 KB Time limit exceeded
6 Halted 0 ms 0 KB -