結果

問題 No.2642 Don't cut line!
コンテスト
ユーザー nono00
提出日時 2024-02-20 17:44:31
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,360 bytes
コンパイル時間 3,068 ms
コンパイル使用メモリ 273,260 KB
実行使用メモリ 33,764 KB
最終ジャッジ日時 2024-09-29 03:47:04
合計ジャッジ時間 9,005 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 1 TLE * 1 -- * 31
権限があれば一括ダウンロードができます

ソースコード

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 max_height = 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);
                    if (max_height < res + 1) {
                        max_height = res + 1;
                        max_i = i;
                    }
                }
                if (max_i != 0) {
                    std::swap(graph[u][0], graph[u][max_i]);
                }
                return max_height;
            };
            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] = 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() {
    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;
    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;
    }
    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) {
        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