結果
問題 | No.2642 Don't cut line! |
ユーザー |
|
提出日時 | 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 |
ソースコード
#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 -> indexHLD(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) { //pathfor (;; 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) { //subtreeq(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;}