結果

問題 No.2642 Don't cut line!
ユーザー ponjuiceponjuice
提出日時 2024-02-15 17:38:28
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 211 ms / 4,000 ms
コード長 3,130 bytes
コンパイル時間 2,741 ms
コンパイル使用メモリ 221,860 KB
実行使用メモリ 33,308 KB
最終ジャッジ日時 2024-09-29 03:31:37
合計ジャッジ時間 8,524 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 207 ms
33,188 KB
testcase_02 AC 210 ms
33,308 KB
testcase_03 AC 199 ms
32,160 KB
testcase_04 AC 201 ms
32,160 KB
testcase_05 AC 206 ms
32,548 KB
testcase_06 AC 105 ms
6,820 KB
testcase_07 AC 110 ms
6,816 KB
testcase_08 AC 109 ms
6,820 KB
testcase_09 AC 107 ms
6,816 KB
testcase_10 AC 108 ms
6,816 KB
testcase_11 AC 106 ms
6,816 KB
testcase_12 AC 111 ms
6,820 KB
testcase_13 AC 106 ms
6,816 KB
testcase_14 AC 108 ms
6,816 KB
testcase_15 AC 110 ms
6,816 KB
testcase_16 AC 171 ms
13,952 KB
testcase_17 AC 153 ms
28,636 KB
testcase_18 AC 167 ms
30,212 KB
testcase_19 AC 119 ms
23,376 KB
testcase_20 AC 92 ms
12,592 KB
testcase_21 AC 107 ms
6,820 KB
testcase_22 AC 127 ms
11,136 KB
testcase_23 AC 211 ms
32,228 KB
testcase_24 AC 97 ms
16,768 KB
testcase_25 AC 98 ms
15,232 KB
testcase_26 AC 113 ms
9,216 KB
testcase_27 AC 135 ms
22,416 KB
testcase_28 AC 200 ms
29,972 KB
testcase_29 AC 109 ms
10,880 KB
testcase_30 AC 103 ms
13,696 KB
testcase_31 AC 161 ms
25,656 KB
testcase_32 AC 103 ms
12,800 KB
testcase_33 AC 2 ms
6,824 KB
testcase_34 AC 2 ms
6,816 KB
testcase_35 AC 2 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

struct UF{
    int n;
    vector<int> par;

    UF(int _n) : n(_n), par(_n, -1) {}

    int root(int p){
        if(par[p] < 0) return p;
        return par[p] = root(par[p]);
    }

    bool same(int l, int r){
        return root(l) == root(r);
    }

    void merge(int l, int r){
        if(same(l, r)) return;
        l = root(l);
        r = root(r);
        if(par[l] > par[r]) swap(l, r);
        par[l] += par[r];
        par[r] = l;
    }
};

int main(){
    ll n, m, c;
    cin >> n >> m >> c;
    vector<pair<int, int>> edges(m);
    vector<ll> w(m);
    vector<ll> p(m);
    for(int i = 0; i < m; i++){
        cin >> edges[i].first >> edges[i].second >> w[i] >> p[i];
        edges[i].first--, edges[i].second--;
    }

    vector<int> Kruskal(m);
    iota(Kruskal.begin(), Kruskal.end(), 0);
    sort(Kruskal.begin(), Kruskal.end(), [&](int l,int r){
        return w[l] < w[r];
    });
    UF uf(n);
    vector<vector<pair<int,ll>>> graph(n);
    ll W = 0, P = 0;
    
    for(int i = 0; i < m; i++){
        if(!uf.same(edges[Kruskal[i]].first, edges[Kruskal[i]].second)){
            uf.merge(edges[Kruskal[i]].first, edges[Kruskal[i]].second);
            graph[edges[Kruskal[i]].first].emplace_back(edges[Kruskal[i]].second, w[Kruskal[i]]);
            graph[edges[Kruskal[i]].second].emplace_back(edges[Kruskal[i]].first, w[Kruskal[i]]);
            W += w[Kruskal[i]];
            P = max(P, p[Kruskal[i]]);
        }
    }

    if(W > c){
        cout << -1 << endl;
        return 0;
    }

    vector<vector<pair<int,ll>>> db(10, vector<pair<int,ll>>(n, {-1, 0}));
    vector<int> depth(n, 0);
    auto dfs = [&](auto&& dfs, int nw, int par)->void {
        for(auto [to, cost] : graph[nw]){
            if(to != par){
                depth[to] = depth[nw] + 1;
                db[0][to] = {nw, cost};
                dfs(dfs, to, nw);
            }
        }
    };
    dfs(dfs, 0, -1);
    for(int i = 1; i < 10; i++){
        for(int j = 0; j < n; j++){
            if(db[i-1][j].first != -1){
                db[i][j] = {db[i-1][db[i-1][j].first].first, max(db[i-1][db[i-1][j].first].second, db[i-1][j].second)};
            }
        }
    }
    
    for(int i = 0; i < m; i++){
        if(p[i] <= P)continue;
        auto[u, v] = edges[i];
        if(depth[u] < depth[v]) swap(u, v);
        ll mxW = 0;
        for(int i = 9; i >= 0; i--){
            if(db[i][u].first != -1 && depth[db[i][u].first] >= depth[v]){
                mxW = max(mxW, db[i][u].second);
                u = db[i][u].first;
            }
        }
        if(u != v){
            for(int i = 9; i > 0; i--){
                if(db[i][u].first != db[i][v].first){
                    mxW = max(mxW, db[i][u].second);
                    mxW = max(mxW, db[i][v].second);
                    u = db[i][u].first;
                    v = db[i][v].first;
                }
            }
            mxW = max(mxW, db[0][u].second);
            mxW = max(mxW, db[0][v].second);

        }
        if(W - mxW + w[i] <= c) P = p[i];
    }

    cout << P << endl;
}
0