結果
| 問題 | No.2642 Don't cut line! |
| コンテスト | |
| ユーザー |
 kwm_t
|
| 提出日時 | 2026-04-11 04:05:16 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 137 ms / 4,000 ms |
| コード長 | 6,303 bytes |
| 記録 | |
| コンパイル時間 | 4,898 ms |
| コンパイル使用メモリ | 388,124 KB |
| 実行使用メモリ | 50,176 KB |
| 最終ジャッジ日時 | 2026-04-11 04:05:28 |
| 合計ジャッジ時間 | 10,563 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 33 |
ソースコード
#include <bits/stdc++.h>
#include <atcoder/all>
//using namespace std;
using namespace atcoder;
//using mint = modint1000000007;
//const int mod = 1000000007;
using mint = modint998244353;
const int mod = 998244353;
//const int INF = 1e9;
//const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; --i)
#define rrep2(i,l,r)for(int i=(r) - 1;i>=(l);--i)
#define all(x) (x).begin(),(x).end()
#define allR(x) (x).rbegin(),(x).rend()
#define P pair<int,int>
template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }
#ifndef KWM_T_GRAPH_HEAVY_LIGHT_DECOMPOSITION_HPP
#define KWM_T_GRAPH_HEAVY_LIGHT_DECOMPOSITION_HPP
#include <vector>
#include <algorithm>
/**
* @brief Heavy-Light Decomposition（HLD, 重軽分解）のコア実装
*
* 木をパス・部分木クエリに適した区間に分解する。
* データ構造（Segment Tree / Lazy Segment Tree など）は外部に持たせる設計。
*
* 典型用途:
* - LCA（Lowest Common Ancestor）
* - 木上のパスクエリ（和・最小値・xorなど）
* - パス更新（Lazy SegTreeと組み合わせ）
* - 部分木クエリ
*
* 計算量:
* - build: O(N)
* - lca / la / dist: O(log N)
* - for_each_path: O(log N) 回の区間分割
*
* @tparam
* 特になし（グラフは vector<vector<int>> で受け取る）
*
* @param
* g: 隣接リスト形式の木（0-indexed）
*
* 制約 / 注意:
* - 木であること（連結・サイクルなし）
* - rootはbuild時に指定可能（デフォルト0）
* - 非可換演算の場合は、for_each_pathの順序に注意して自分で管理すること
* - 辺クエリは「子ノードに値を持たせる」ことで対応
*
* 使用例:
* HLD hld(g);
* hld.build();
*
* // パスクエリ
* long long res = 0;
* hld.for_each_path(u, v, [&](int l, int r) {
* res += seg.prod(l, r);
* });
*
* verified:
* - AtCoder Library Practice Contest
* - ABC / ARC 木クエリ系問題
*/
namespace kwm_t::graph {
class HeavyLightDecomposition {
private:
int n;
std::vector<std::vector<int>> g;
std::vector<int> sz, par, depth;
std::vector<int> in, out, head, rev;
void dfs_sz(int v, int p) {
par[v] = p;
sz[v] = 1;
for (auto& to : g[v]) {
if (to == p) continue;
depth[to] = depth[v] + 1;
dfs_sz(to, v);
sz[v] += sz[to];
if (sz[to] > sz[g[v][0]] || g[v][0] == p) {
std::swap(to, g[v][0]);
}
}
}
void dfs_hld(int v, int p, int& t) {
in[v] = t;
rev[t] = v;
++t;
for (auto to : g[v]) {
if (to == p) continue;
head[to] = (to == g[v][0] ? head[v] : to);
dfs_hld(to, v, t);
}
out[v] = t;
}
public:
HeavyLightDecomposition(const std::vector<std::vector<int>>& graph)
: n(graph.size()), g(graph),
sz(n), par(n), depth(n),
in(n), out(n), head(n), rev(n) {}
void build(int root = 0) {
depth[root] = 0;
dfs_sz(root, -1);
int t = 0;
head[root] = root;
dfs_hld(root, -1, t);
}
// LCA
int lca(int u, int v) const {
while (head[u] != head[v]) {
if (depth[head[u]] > depth[head[v]]) u = par[head[u]];
else v = par[head[v]];
}
return (depth[u] < depth[v] ? u : v);
}
// k-th ancestor
int la(int v, int k) const {
while (true) {
int h = head[v];
if (in[v] - k >= in[h]) return rev[in[v] - k];
k -= (in[v] - in[h] + 1);
v = par[h];
}
}
int dist(int u, int v) const {
int w = lca(u, v);
return depth[u] + depth[v] - 2 * depth[w];
}
// ===== 頂点パス =====
// 区間 [l, r) をコールバックに渡す
template <class F>
void for_each_path(int u, int v, const F& f) const {
while (head[u] != head[v]) {
if (depth[head[u]] > depth[head[v]]) {
f(in[head[u]], in[u] + 1);
u = par[head[u]];
}
else {
f(in[head[v]], in[v] + 1);
v = par[head[v]];
}
}
if (depth[u] > depth[v]) std::swap(u, v);
f(in[u], in[v] + 1);
}
// ===== 辺パス =====
template <class F>
void for_each_path_edge(int u, int v, const F& f) const {
while (head[u] != head[v]) {
if (depth[head[u]] > depth[head[v]]) {
f(in[head[u]], in[u] + 1);
u = par[head[u]];
}
else {
f(in[head[v]], in[v] + 1);
v = par[head[v]];
}
}
if (u == v) return;
if (depth[u] > depth[v]) std::swap(u, v);
f(in[u] + 1, in[v] + 1);
}
// ===== 部分木 =====
template <class F>
void for_each_subtree(int v, const F& f) const {
f(in[v], out[v]);
}
// ===== getter =====
int get_in(int v) const { return in[v]; }
int get_out(int v) const { return out[v]; }
int get_rev(int i) const { return rev[i]; }
int get_par(int v) const { return par[v]; }
int get_depth(int v) const { return depth[v]; }
};
}
#endif // KWM_T_GRAPH_HEAVY_LIGHT_DECOMPOSITION_HPP
using S = long long;
S op(S a, S b) { return std::max(a, b); }
S ee() { return 0; }
int main() {
using namespace std;
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m; cin >> n >> m;
long long c; cin >> c;
struct Edge {
int u, v, w, p;
bool operator<(const Edge& other)const {
return w < other.w;
}
};
vector<Edge>e(m);
rep(i, m) {
cin >> e[i].u >> e[i].v >> e[i].w >> e[i].p;
e[i].u--;
e[i].v--;
}
sort(all(e));
vector<vector<int>>to(2 * n - 1);
dsu uf(n);
int ans = 0;
long long mncost = 0;
vector<S>v(n * 2 - 1);
int idx = n;
for (auto &e : e) {
if (uf.same(e.u, e.v))continue;
to[e.u].emplace_back(idx);
to[idx].emplace_back(e.u);
to[idx].emplace_back(e.v);
to[e.v].emplace_back(idx);
chmax(ans, e.p);
mncost += e.w;
uf.merge(e.u, e.v);
v[idx] = e.w;
idx++;
}
if (mncost > c) {
cout << -1 << endl;
return 0;
}
kwm_t::graph::HeavyLightDecomposition hld(to);
hld.build();
vector<S>v2(n * 2 - 1);
rep(i, n * 2 - 1)v2[hld.get_in(i)] = v[i];
atcoder::segtree<S, op, ee>seg(v2);
for (auto &e : e) {
if (e.p <= ans) continue;
long long get = 0;
auto f = [&](int l, int r) {
get = op(get, seg.prod(l, r));
};
hld.for_each_path(e.u, e.v, f);
if (mncost - get + e.w <= c)ans = e.p;
}
cout << ans << endl;
}