結果
問題 | No.2642 Don't cut line! |
ユーザー |
|
提出日時 | 2024-02-20 00:59:19 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 201 ms / 4,000 ms |
コード長 | 6,733 bytes |
コンパイル時間 | 5,057 ms |
コンパイル使用メモリ | 272,308 KB |
最終ジャッジ日時 | 2025-02-19 17:51:48 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#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-subtreetypedef vector<vector<int> > Graph;struct HLDecomposition {int n;Graph G;vector<int> vid, inv, par, depth, subsize, head, prev, next, type;// constructHLDecomposition() { }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/38833623void 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#1void subtree_edges(int v, const function<void(int,int)> &f) {f(vid[v] + 1, vid[v] + subsize[v]);}// LCAint 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;}