結果

問題 No.2642 Don't cut line!
ユーザー pitPpitP
提出日時 2024-02-20 00:59:19
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 146 ms / 4,000 ms
コード長 6,733 bytes
コンパイル時間 4,447 ms
コンパイル使用メモリ 284,496 KB
実行使用メモリ 25,480 KB
最終ジャッジ日時 2024-09-29 03:40:49
合計ジャッジ時間 8,851 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 146 ms
25,356 KB
testcase_02 AC 139 ms
25,224 KB
testcase_03 AC 141 ms
25,396 KB
testcase_04 AC 141 ms
25,228 KB
testcase_05 AC 138 ms
25,480 KB
testcase_06 AC 75 ms
6,816 KB
testcase_07 AC 74 ms
6,816 KB
testcase_08 AC 72 ms
6,816 KB
testcase_09 AC 73 ms
6,816 KB
testcase_10 AC 73 ms
6,820 KB
testcase_11 AC 72 ms
6,816 KB
testcase_12 AC 78 ms
6,816 KB
testcase_13 AC 73 ms
6,820 KB
testcase_14 AC 75 ms
6,820 KB
testcase_15 AC 75 ms
6,820 KB
testcase_16 AC 62 ms
11,784 KB
testcase_17 AC 115 ms
22,924 KB
testcase_18 AC 124 ms
23,980 KB
testcase_19 AC 92 ms
19,628 KB
testcase_20 AC 65 ms
10,624 KB
testcase_21 AC 39 ms
6,820 KB
testcase_22 AC 45 ms
9,856 KB
testcase_23 AC 141 ms
24,852 KB
testcase_24 AC 70 ms
13,696 KB
testcase_25 AC 84 ms
12,672 KB
testcase_26 AC 106 ms
8,064 KB
testcase_27 AC 83 ms
17,024 KB
testcase_28 AC 128 ms
23,612 KB
testcase_29 AC 104 ms
9,344 KB
testcase_30 AC 100 ms
11,904 KB
testcase_31 AC 102 ms
20,992 KB
testcase_32 AC 94 ms
10,752 KB
testcase_33 AC 2 ms
6,820 KB
testcase_34 AC 2 ms
6,816 KB
testcase_35 AC 1 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
istream &operator>>(istream &is, modint &a) { long long v; is >> v; a = v; return is; }
ostream &operator<<(ostream &os, const modint &a) { return os << a.val(); }
istream &operator>>(istream &is, modint998244353 &a) { long long v; is >> v; a = v; return is; }
ostream &operator<<(ostream &os, const modint998244353 &a) { return os << a.val(); }
istream &operator>>(istream &is, modint1000000007 &a) { long long v; is >> v; a = v; return is; }
ostream &operator<<(ostream &os, const modint1000000007 &a) { return os << a.val(); } 

typedef long long ll;
typedef vector<vector<int>> Graph;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define FOR(i,l,r) for (int i = l;i < (int)(r); i++)
#define rep(i,n) for (int i = 0;i < (int)(n); i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define my_sort(x) sort(x.begin(), x.end())
#define my_max(x) *max_element(all(x))
#define my_min(x) *min_element(all(x))
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll LINF = (1LL<<62) - 1;
const int MOD = 998244353;
const int MOD2 = 1e9+7;
const double PI = acos(-1);
vector<int> di = {1,0,-1,0};
vector<int> dj = {0,1,0,-1};

#ifdef LOCAL
#  include <debug_print.hpp>
#  define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#  define debug(...) (static_cast<void>(0))
#endif

// HL-Decomposition
// vid: id of v after HL-Decomposition
// inv: inv[vid[v]] = v
// par: id of parent
// depth
// subsize: size of subtree
// head: head-id in the heavy-path
// prev, next: prev-id, next-id in the heavy-path
// type: the id of tree for forest
// vend: the last-id of node in v-subtree
typedef vector<vector<int> > Graph;
struct HLDecomposition {
    int n;
    Graph G;
    vector<int> vid, inv, par, depth, subsize, head, prev, next, type;
    
    // construct
    HLDecomposition() { }
    HLDecomposition(const Graph &G_) :
        n((int)G_.size()), G(G_),
        vid(n, -1), inv(n), par(n), depth(n), subsize(n, 1),
        head(n), prev(n, -1), next(n, -1), type(n) { }
    void build(vector<int> roots = {0}) {
        int curtype = 0, pos = 0;
        for (auto r : roots) decide_heavy_edge(r), reconstruct(r, curtype++, pos);
    }
    void decide_heavy_edge(int r) {
        stack<pair<int,int> > st;
        par[r] = -1, depth[r] = 0;
        st.emplace(r, 0);
        while (!st.empty()) {
            int v = st.top().first;
            int &i = st.top().second;
            if (i < (int)G[v].size()) {
                int e = G[v][i++];
                if (e == par[v]) continue;
                par[e] = v, depth[e] = depth[v] + 1;
                st.emplace(e, 0);
            }
            else {
                st.pop();
                int maxsize = 0;
                for (auto e : G[v]) {
                    if (e == par[v]) continue;
                    subsize[v] += subsize[e];
                    if (maxsize < subsize[e]) maxsize = subsize[e], prev[e] = v, next[v] = e;
                }
            }
        }
    }
    void reconstruct(int r, int curtype, int &pos) {
        stack<int> st({r});
        while (!st.empty()) {
            int start = st.top(); st.pop();
            for (int v = start; v != -1; v = next[v]) {
                type[v] = curtype;
                vid[v] = pos++;
                inv[vid[v]] = v;
                head[v] = start;
                for (auto e : G[v]) if (e != par[v] && e != next[v]) st.push(e);
            }
        }
    }
    
    // node query [u, v], f([left, right])
    void foreach_nodes(int u, int v, const function<void(int,int)> &f) {
        while (true) {
            if (vid[u] > vid[v]) swap(u, v);
            f(max(vid[head[v]], vid[u]), vid[v]);
            if (head[u] != head[v]) v = par[head[v]];
            else break;
        }
    }
    
    // edge query [u, v], f([left, right])
    void foreach_edges(int u, int v, const function<void(int,int)> &f) {
        while (true) {
            if (vid[u] > vid[v]) swap(u, v);
            if (head[u] != head[v]) {
                f(vid[head[v]], vid[v]);
                v = par[head[v]];
            }
            else {
                if (u != v) {
                    f(vid[u]+1, vid[v]);
                }
                break;
            }
        }
    }

    // https://atcoder.jp/contests/abc138/submissions/38833623
    void subtree_nodes(int v, const function<void(int,int)> &f) {
        f(vid[v],vid[v]+subsize[v]);
    }

    // https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=7464630#1
    void subtree_edges(int v, const function<void(int,int)> &f) {
        f(vid[v] + 1, vid[v] + subsize[v]);
    }

    // LCA
    int lca(int u, int v) {
        while (true) {
            if (vid[u] > vid[v]) swap(u, v);
            if (head[u] == head[v]) return u;
            v = par[head[v]];
        }
    }
};
// https://drken1215.hatenablog.com/entry/2018/08/14/193500

// 区間更新、区間最大値
using S = long long;
using F = long long;

const S INF = 8e18;
const F ID = 8e18;

S op(S a, S b){ return std::max(a, b); }
S e(){ return -INF; }
S mapping(F f, S x){ return (f == ID ? x : f); }
F composition(F f, F g){ return (f == ID ? g : f); }
F id(){ return ID; }


int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int N, K; cin >> N >> K;
    ll C; cin >> C;
    vector<int> u(K), v(K), w(K), p(K);
    rep(i,K) {
        cin >> u[i] >> v[i] >> w[i] >> p[i];
        u[i]--;
        v[i]--;
    }

    vector<pii> edges(K); // (weight, idx);
    rep(i,K) edges[i] = make_pair(w[i], i);
    sort(all(edges));
    dsu uf(N);

    ll cost = 0;
    int ans = 0;
    Graph g(N);
    vector<int> edx;
    for(auto [weight, idx] : edges){
        if(uf.same(u[idx], v[idx]))continue;
        cost += (ll)weight;
        uf.merge(u[idx], v[idx]);
        g[u[idx]].push_back(v[idx]);
        g[v[idx]].push_back(u[idx]);
        chmax(ans, p[idx]);
        edx.push_back(idx);
    }
    if(cost > C){
        cout << -1 << endl;
        return 0;
    }

    HLDecomposition hld(g);
    hld.build();
    vector<S> dat(N);
    lazy_segtree<S,op,e,F,mapping,composition,id> seg(dat);
    for(int idx : edx){
        hld.foreach_edges(v[idx], u[idx], 
        [&](int l, int r){seg.apply(l, r + 1, w[idx]);});
    }

    rep(idx,K){
        ll mw = 0;
        hld.foreach_edges(v[idx], u[idx], [&](int l, int r){mw = max(mw, seg.prod(l, r + 1));});
        if(cost - mw + (ll)w[idx] <= C){
            chmax(ans, p[idx]);
        }
    }

    cout << ans << endl;
}
0