結果

問題 No.2642 Don't cut line!
ユーザー pitP
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0