結果

問題 No.2642 Don't cut line!
コンテスト
ユーザー GOTKAKO
提出日時 2024-04-06 03:47:31
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 320 ms / 4,000 ms
コード長 5,438 bytes
コンパイル時間 3,202 ms
コンパイル使用メモリ 231,780 KB
最終ジャッジ日時 2025-02-20 22:23:11
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

struct HLD2{
    //2.辺のみパターン.
    //辺のコストを頂点にするのが楽そう.
    vector<vector<int>> Graph;
    int n = 0,tim = 0;
    vector<int> dist,in,out,siz,head,pre,par;
    vector<long long> cost;
    long long e(){return 0;}

    void rearrange(vector<vector<pair<int,long long>>> &G){
        n = G.size()*2-1;
        Graph.resize(n); cost.resize(n,e());
        int edge = G.size();
        for(int i=0; i<G.size(); i++){
            for(auto [to,e] : G.at(i)){
                if(to < i) continue;
                cost.at(edge) = e;
                Graph.at(i).push_back(edge);
                Graph.at(edge).push_back(i);
                Graph.at(to).push_back(edge);
                Graph.at(edge++).push_back(to);
            }
        }
    }

    vector<long long> make(vector<vector<pair<int,long long>>> &G){
        rearrange(G); 
        dist.resize(n),in.resize(n),siz.resize(n,1);
        head.resize(n),par.resize(n);
        dfs1(0,-1,0); dfs2(0,-1);
        vector<long long> ret(n);
        for(int i=0; i<n; i++) ret.at(in.at(i)) = cost.at(i);
        return ret;
    }
    
    void dfs1(int pos,int back,int d){
        par.at(pos) = back; dist.at(pos) = d;
        if(Graph.at(pos).size()) if(Graph.at(pos).at(0)) swap(Graph.at(pos).at(0),Graph.at(pos).back());
        for(auto &to : Graph.at(pos)){
            if(to == back) continue;
            dfs1(to,pos,d+1);
            siz.at(pos) += siz.at(to);
            if(siz.at(Graph.at(pos).at(0)) < siz.at(to)) swap(Graph.at(pos).at(0),to);
        }
    }
    void dfs2(int pos,int back){
        in.at(pos) = tim++;
        for(auto to : Graph.at(pos)){
            if(to == back) continue;
            if(to == Graph.at(pos).at(0)) head.at(to) = head.at(pos);
            else head.at(to) = to;
            dfs2(to,pos);
        } 
    }
 
    vector<pair<int,int>> findpath(int u,int v){
		//dfs行きがけ順に並べた頂点のセグ木の区間を返す.
		//行きがけ順はrep(0-n)give[in[i]]=A[i].
	    //交換法則が成り立たない時は修正必須.
        vector<pair<int,int>> ret;
        while(head.at(u) != head.at(v)){
            if(dist.at(head.at(u)) > dist.at(head.at(v))) swap(u,v);
            ret.push_back({in.at(head.at(v)),in.at(v)+1});
            v = par.at(head.at(v));
        }
        if(in.at(u) > in.at(v)) swap(u,v);
        ret.push_back({in.at(u),in.at(v)+1});
        return ret;
    }
};

using SS = long long;
class SegmentTree{
    public:
    int siz = 1;
    vector<SS> dat;
 
    SS op(SS a, SS b){return max(a,b);}
    SS e(){return 0;}
    void renew (SS &a,SS x){
        //a = op(a,x);
        a = x;
        //その他.
    }
 
    void make(int N){
        while(siz < N) siz *= 2;
        dat.resize(siz*2,e());
    }
 
    void make2(int N,vector<SS> &A){
        make(N);
        for(int i=0; i<N; i++){
            int pos = i+siz;
            dat.at(pos) = A.at(i);
        }
        for(int i=siz-1; i>0; i--) dat.at(i) = op(dat.at(i*2),dat.at(i*2+1));
    }
 
    void update(int pos,SS x){
        pos = pos+siz;
        renew(dat.at(pos),x);
        while(pos != 1){
            pos = pos/2;
            dat.at(pos) = op(dat.at(pos*2),dat.at(pos*2+1));
        }
    }
 
SS findans(int l, int r){
    SS retl = e(),retr = e();
    l += siz,r += siz;
    while(l < r){
        if(l&1) retl = op(retl,dat.at(l++));
        if(r&1) retr = op(dat.at(--r),retr);
        l >>= 1; r >>= 1;
    }
    return op(retl,retr);
}
 
    SS get(int pos){return dat.at(pos+siz);}
    SS rangeans(int l, int r){return findans(l,r);}
    SS allrange(){return findans(0,siz);}
 
    //ノーマルセグ木 二分探索は実装してない.
};

class UnionFind{
    public:
    vector<int> par,siz;
 
    void make(int N){
        par.resize(N,-1);
        siz.resize(N,1);
    }
 
    int root(int x){
        if(par.at(x) == -1) return x;
        else return par.at(x) = root(par.at(x));
    }
 
    void unite(int u, int v){
        u = root(u),v = root(v);
        if(u == v) return;
        if(siz.at(u) < siz.at(v)) swap(u,v);
 
        par.at(v) = u;
        siz.at(u) += siz.at(v);
    }
 
    bool issame(int u, int v){
        if(root(u) == root(v)) return true;
        else return false;
    }
};

int main() {
    long long N,K,C; cin >> N >> K >> C;
    UnionFind Z; Z.make(N);
    vector<tuple<int,int,int,int>> WPUV(K);
    for(auto &[w,p,u,v] : WPUV) cin >> u >> v >> w >> p,u--,v--;
    sort(WPUV.begin(),WPUV.end());

    long long nowc = 0; int nowp = -1;
    vector<bool> already;
    vector<vector<pair<int,long long>>> Graph(N);
    for(auto &[w,p,u,v] : WPUV){
        if(Z.issame(u,v)){already.push_back(false); continue;}
        already.push_back(true);
        Z.unite(u,v);
        Graph.at(u).push_back({v,w});
        Graph.at(v).push_back({u,w});
        nowc += w,nowp = max(nowp,p);
    }
    if(nowc > C){cout << -1 << endl; return 0;}
    
    HLD2 H; 
    vector<long long> give = H.make(Graph);
    SegmentTree S; S.make2(H.n,give);

    for(int i=0; i<K; i++){
        if(already.at(i)) continue;
        auto &[w,p,u,v] = WPUV.at(i);
        if(p <= nowp) continue;
        auto LR = H.findpath(u,v);
        long long maxc = S.e();
        for(auto &[l,r] : LR) maxc = S.op(maxc,S.rangeans(l,r));
        if(nowc+w-maxc > C) continue;
        nowp = p;
    }
    cout << nowp << endl;
}
0