結果

問題 No.2642 Don't cut line!
ユーザー kenken714kenken714
提出日時 2024-02-19 22:55:46
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 5,744 bytes
コンパイル時間 2,910 ms
コンパイル使用メモリ 229,004 KB
実行使用メモリ 37,776 KB
最終ジャッジ日時 2024-02-20 12:48:05
合計ジャッジ時間 8,648 ms
ジャッジサーバーID
（参考情報） 		judge16 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 176 ms
37,776 KB
testcase_02 AC 183 ms
37,776 KB
testcase_03 AC 176 ms
37,776 KB
testcase_04 AC 177 ms
37,776 KB
testcase_05 AC 173 ms
37,776 KB
testcase_06 AC 115 ms
33,500 KB
testcase_07 AC 116 ms
33,500 KB
testcase_08 AC 119 ms
33,500 KB
testcase_09 AC 119 ms
33,500 KB
testcase_10 AC 124 ms
33,500 KB
testcase_11 AC 116 ms
33,500 KB
testcase_12 AC 122 ms
33,500 KB
testcase_13 AC 120 ms
33,500 KB
testcase_14 AC 120 ms
33,500 KB
testcase_15 AC 122 ms
33,500 KB
testcase_16 AC 141 ms
37,776 KB
testcase_17 AC 137 ms
37,392 KB
testcase_18 AC 142 ms
37,648 KB
testcase_19 AC 110 ms
37,008 KB
testcase_20 AC 98 ms
33,936 KB
testcase_21 AC 116 ms
33,552 KB
testcase_22 AC 111 ms
37,136 KB
testcase_23 AC 172 ms
37,776 KB
testcase_24 AC 97 ms
32,272 KB
testcase_25 AC 103 ms
32,400 KB
testcase_26 AC 118 ms
33,552 KB
testcase_27 AC 114 ms
34,652 KB
testcase_28 AC 164 ms
37,520 KB
testcase_29 AC 121 ms
33,936 KB
testcase_30 AC 108 ms
34,652 KB
testcase_31 AC 140 ms
37,264 KB
testcase_32 AC 112 ms
33,936 KB
testcase_33 AC 16 ms
28,976 KB
testcase_34 AC 16 ms
28,976 KB
testcase_35 AC 15 ms
28,976 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1ll << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD (ll)1000000007
#define P pair<ll, ll>

//つよいせぐつりー！
struct LazySegTree { //参照は i + sz - 1 だよ～;
    ll sz;
    vector<ll> node, lazy;
    vector<bool> lazyFlag;
    LazySegTree(ll n) {
        sz = 1;
        while (sz < n) sz *= 2;
        node.resize(2 * sz - 1);//
        lazy.resize(2 * sz - 1);//
        lazyFlag.resize(2 * sz - 1);
    }
    void eval(ll k, ll l, ll r) {
        if (lazyFlag[k]) {
            node[k] += lazy[k];//
            if (r - l > 1) {
                lazy[2 * k + 1] += lazy[k] / 2;//
                lazy[2 * k + 2] += lazy[k] / 2;//
                lazyFlag[2 * k + 1] = lazyFlag[2 * k + 2] = true;
            }
            lazyFlag[k] = false;
            lazy[k] = 0;//
        }
    }
    void update(ll a, ll b, ll x, ll k = 0, ll l = 0, ll r = -1) {
        if (r < 0) r = sz;
        eval(k, l, r);
        if (b <= l || r <= a) return;
        if (a <= l && r <= b) {
            lazy[k] += (r - l) * x;//
            lazyFlag[k] = true;
            eval(k, l, r);

        }
        else {
            update(a, b, x, 2 * k + 1, l, (l + r) / 2);
            update(a, b, x, 2 * k + 2, (l + r) / 2, r);
            node[k] = node[2 * k + 1] + node[2 * k + 2];//
        }
    }
    void update(ll a, ll x) {
        update(a, a + 1, x);
    }
    ll query(ll a, ll b, ll k = 0, ll l = 0, ll r = -1) {
        if (r < 0) r = sz;
        eval(k, l, r);
        if (b <= l || r <= a) return 0;//
        if (a <= l && r <= b) return node[k];
        ll vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
        ll vr = query(a, b, 2 * k + 2, (l + r) / 2, r);
        return vl + vr;//
    }
    void init() {
        REPR(i, sz - 2) node[i] = node[2 * i + 1] + node[2 * i + 2];//
    }
};

struct HLD {//いつもの
	vector<ll> g[510000];
	vector<ll> sz, in, out, head, rev, par, dep; //rev = in -> index
	HLD(ll n) : sz(n), in(n), out(n), head(n), rev(n), par(n), dep(n) {};
	void dfs_sz(ll a, ll p, ll b) {
		par[a] = p;
		sz[a] = 1;
		dep[a] = b;
		if (g[a].size() && g[a][0] == p) swap(g[a][0], g[a].back());
		for (auto& to : g[a]) {
			if (to == p)continue;
			dfs_sz(to, a, b + 1);
			sz[a] += sz[to];
			if (sz[g[a][0]] < sz[to])swap(g[a][0], to);
		}
	}
	void dfs_hld(ll a, ll p, ll& t) {
		in[a] = t++;
		rev[in[a]] = a;
		for (auto& to : g[a]) {
			if (to == p)continue;
			head[to] = (g[a][0] == to ? head[a] : to);
			dfs_hld(to, a, t);
		}
		out[a] = t;
	}
	void edgeset(ll a, ll b) {
		g[a].push_back(b);
		g[b].push_back(a);
	}
	void build() {
		dfs_sz(0, -1, 0);
		ll t = 0;
		dfs_hld(0, -1, t);
	}
	void input(ll n) {
		REP(i, n - 1) {
			ll a, b;
			cin >> a >> b;
			a--; b--;
			edgeset(a, b);
		}
		build();
	}
	ll la(ll a, ll x) {
		while (1) {
			ll h = head[a];
			if (in[a] - x >= in[h])return rev[in[a] - x];
			x -= in[a] - in[h] + 1;
			a = par[h];
		}
	}
	ll lca(ll a, ll b) {
		for (;; b = par[head[b]]) {
			if (in[a] > in[b])swap(a, b);
			if (head[a] == head[b])return a;
		}
	}
	template< typename Q, typename F >
	ll query(ll a, ll b, ll ti, const Q& q, const F& f, bool edge = false) {
		ll l = ti, r = ti;
		for (;; b = par[head[b]]) {
			if (in[a] > in[b])swap(a, b), swap(l, r);
			if (head[a] == head[b])break;
			l = f(q(in[head[b]], in[b] + 1), l);
		}
		return f(f(q(in[a] + edge, in[b] + 1), l), r);
	}
	template < typename Q >
	void addpath(ll a, ll b, ll x, const Q& q, bool edge = false) { //path
		for (;; b = par[head[b]]) {
			if (in[a] > in[b])swap(a, b);
			if (head[a] == head[b])break;
			q(in[head[b]], in[b] + 1, x);
		}
		return q(in[a] + edge, in[b] + 1, x);
	}
	template < typename Q >
	void addst(ll a, ll x, const Q& q) { //subtree
		q(in[a], out[a], x);
	}
};

struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) { }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

LazySegTree seg(110000);
UnionFind uf(110000);
ll n, m, c, w[210000], p[210000], allw;
P e[210000];
HLD hld(110000);
int main(){
    cin >> n >> m >> c;
    vector<P> v;
    vector<pair<P, ll>> vv;
    REP(i, m){
        ll a, b;
        cin >> a >> b >> w[i] >> p[i];
        a--;
        b--;
        e[i] = P(a, b);
        v.push_back(P(w[i], i));
    }
    sort(ALL(v));
    ll ans = 0;
    REP(i, m){
        ll a = e[v[i].second].first, b = e[v[i].second].second;
        if(!uf.findSet(a, b)){
            allw += v[i].first;
            uf.unionSet(a, b);
            vv.push_back(pair<P, ll>(P(a, b), w[v[i].second]));
            ans = max(ans, p[v[i].second]);
        }
    }
    if(allw > c){
        cout << -1 <<endl;
        return 0;
    }
    hld.build();
    REP(i, vv.size()){
        hld.addpath(vv[i].first.first, vv[i].first.second, vv[i].second, [](ll a, ll b, ll x){seg.update(a, b, x);}, true);
    }
    REP(i, m){
        if(p[i] <= ans)continue;
        ll noww = allw + w[i] - hld.query(e[i].first, e[i].second, 0, [](ll a, ll b){return seg.query(a, b);}, [](ll a, ll b){return max(a, b);}, true );
        if(noww <= c){
            ans = max(ans, p[i]);
        }
    }
    cout << ans << endl;
}
0