結果

問題 No.2642 Don't cut line!
ユーザー kenken714
提出日時 2024-02-19 22:55:46
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 5,744 bytes
コンパイル時間 2,894 ms
コンパイル使用メモリ 220,612 KB
最終ジャッジ日時 2025-02-19 17:30:38
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 32 WA * 1
権限があれば一括ダウンロードができます

ソースコード

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