結果

問題 No.2642 Don't cut line!
ユーザー nono00nono00
提出日時 2024-02-20 18:24:40
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 156 ms / 4,000 ms
コード長 5,627 bytes
コンパイル時間 3,877 ms
コンパイル使用メモリ 276,340 KB
実行使用メモリ 28,064 KB
最終ジャッジ日時 2024-09-29 03:49:47
合計ジャッジ時間 8,473 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 144 ms
27,480 KB
testcase_02 AC 152 ms
28,064 KB
testcase_03 AC 149 ms
25,516 KB
testcase_04 AC 146 ms
25,044 KB
testcase_05 AC 156 ms
26,452 KB
testcase_06 AC 71 ms
7,052 KB
testcase_07 AC 73 ms
7,144 KB
testcase_08 AC 71 ms
7,020 KB
testcase_09 AC 70 ms
7,148 KB
testcase_10 AC 71 ms
7,144 KB
testcase_11 AC 72 ms
7,012 KB
testcase_12 AC 75 ms
7,272 KB
testcase_13 AC 71 ms
7,144 KB
testcase_14 AC 71 ms
7,016 KB
testcase_15 AC 73 ms
7,272 KB
testcase_16 AC 81 ms
14,076 KB
testcase_17 AC 113 ms
22,996 KB
testcase_18 AC 130 ms
22,968 KB
testcase_19 AC 82 ms
19,756 KB
testcase_20 AC 63 ms
10,044 KB
testcase_21 AC 46 ms
7,588 KB
testcase_22 AC 57 ms
12,008 KB
testcase_23 AC 144 ms
25,724 KB
testcase_24 AC 60 ms
11,672 KB
testcase_25 AC 66 ms
10,848 KB
testcase_26 AC 83 ms
7,532 KB
testcase_27 AC 82 ms
18,592 KB
testcase_28 AC 129 ms
23,812 KB
testcase_29 AC 78 ms
8,296 KB
testcase_30 AC 70 ms
10,048 KB
testcase_31 AC 101 ms
20,076 KB
testcase_32 AC 74 ms
10,160 KB
testcase_33 AC 2 ms
6,816 KB
testcase_34 AC 2 ms
6,820 KB
testcase_35 AC 2 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

const int ROOT = 0;

struct Edge {
    int from;
    int to;
    int weight;
    int profit;
    int id;
};

struct UnionFind {
    std::vector<int> data;
    UnionFind(int n): data(n, -1) {}
    int find(int x) {
        if (data[x] < 0) return x;
        return data[x] = find(data[x]);
    }
    bool merge(int lhs, int rhs) {
        lhs = find(lhs);
        rhs = find(rhs);
        if (lhs == rhs) return false;
        if (data[lhs] < data[rhs]) std::swap(lhs, rhs);
        data[rhs] += data[lhs];
        data[lhs] = rhs;
        return true;
    }
};

std::vector<Edge> kruskal(int n, std::vector<Edge> edges) {
    std::sort(edges.begin(), edges.end(), [](Edge lhs, Edge rhs) { return lhs.weight < rhs.weight; });
    UnionFind uf(n);
    std::vector<Edge> res;
    for (auto e: edges) {
        if (uf.merge(e.from, e.to)) {
            res.push_back(e);
        }
    }
    return res;
}

struct SegTree {
    int n;
    std::vector<int> data;
    static constexpr int e = 0;
    SegTree(int n): n(n), data(2 * n, e) {}
    void set(int i, int elem) {
        i += n;
        data[i] = elem;
        for (i >>= 1; i > 0; i >>= 1) {
            data[i] = std::max(data[2 * i], data[2 * i + 1]);
        }
    }
    int prod(int left, int right) {
        int res = e;
        for (left += n, right += n; left < right; left >>= 1, right >>= 1) {
            if (left & 1) res = std::max(res, data[left++]);
            if (right & 1) res = std::max(res, data[--right]);
        }
        return res;
    }
};

struct HLD {
    std::vector<int> parent, head, in, out, depth;
    HLD(std::vector<std::vector<std::pair<int, int>>> graph) {
        int n = graph.size();
        {
            auto dfs = [&](auto self, int u, int p) -> int {
                int subtree = 1;
                int max_subtree = 0;
                int max_i = 0;
                for (int i = 0; i < (int)graph[u].size(); i++) {
                    auto [v, w] = graph[u][i];
                    if (v == p) continue;
                    int res = self(self, v, u);
                    subtree += res;
                    if (max_subtree < res) {
                        max_subtree = res;
                        max_i = i;
                    }
                }
                if (max_i != 0) {
                    std::swap(graph[u][0], graph[u][max_i]);
                }
                return subtree;
            };
            dfs(dfs, ROOT, ROOT);
        }
        parent.resize(n);
        in.resize(n);
        out.resize(n);
        head.resize(n, -1);
        depth.resize(n);
        int now = 0;
        auto dfs = [&](auto self, int u, int p) -> void {
            if (head[u] == -1) {
                head[u] = u;
            }
            in[u] = now++;
            parent[u] = p;
            for (int i = 0; i < (int)graph[u].size(); i++) {
                auto [v, w] = graph[u][i];
                if (v == p) continue;
                if (i == 0) {
                    head[v] = head[u];
                }
                depth[v] = depth[u] + 1;
                self(self, v, u);
            }
            out[u] = now;
        };
        dfs(dfs, ROOT, ROOT);
    }
    int edge(int u) {
        return in[u];
    }
    int lca(int lhs, int rhs) {
        if (depth[head[lhs]] < depth[head[rhs]]) std::swap(lhs, rhs);
        while (head[lhs] != head[rhs]) {
            lhs = parent[head[lhs]];
            if (depth[head[lhs]] < depth[head[rhs]]) std::swap(lhs, rhs);
        }
        if (depth[lhs] < depth[rhs]) return lhs;
        return rhs;
    }
    std::vector<std::pair<int, int>> path(int lhs, int rhs) {
        int p = lca(lhs, rhs);
        std::vector<std::pair<int, int>> res;
        for (auto v: {lhs, rhs}) {
            while (head[p] != head[v]) {
                res.emplace_back(in[head[v]], in[v] + 1);
                v = parent[head[v]];
            }
            res.emplace_back(in[p] + 1, in[v] + 1);
        }
        return res;
    }
};

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int n, k;
    long long c;
    std::cin >> n >> k >> c;
    std::vector<Edge> edges;
    for (int i = 0; i < k; i++) {
        int u, v, w, p;
        std::cin >> u >> v >> w >> p;
        u--;
        v--;
        edges.emplace_back(u, v, w, p, i);
    }
    std::vector<std::vector<std::pair<int, int>>> graph(n);
    auto tree_edges = kruskal(n, edges);
    long long cost_sum = 0;
    std::vector<bool> used(k);
    for (auto e: tree_edges) {
        graph[e.from].emplace_back(e.to, e.weight);
        graph[e.to].emplace_back(e.from, e.weight);
        cost_sum += e.weight;
        used[e.id] = true;
    }
    if (cost_sum > c) {
        std::cout << -1 << '\n';
        return 0;
    }
    std::vector<int> weights(n);
    auto dfs = [&](auto self, int u, int p) -> void {
        for (auto [v, w]: graph[u]) {
            if (v == p) {
                weights[u] = w;
            } else {
                self(self, v, u);
            }
        }
    };
    dfs(dfs, ROOT, ROOT);

    HLD hld(graph);
    SegTree segtree(n);
    for (int i = 1; i < n; i++) {
        segtree.set(hld.edge(i), weights[i]);
    }
    int ans = -1;
    for (auto e: edges) {
        if (used[e.id]) {
            ans = std::max(ans, e.profit);
            continue;
        }
        int max_cost = 0;
        for (auto [l, r]: hld.path(e.from, e.to)) {
            max_cost = std::max(max_cost, segtree.prod(l, r));
        }
        if (cost_sum - max_cost + e.weight <= c) {
            ans = std::max(ans, e.profit);
        }
    }
    std::cout << ans << '\n';
}
0