結果

問題 No.2642 Don't cut line!
ユーザー Aeren
提出日時 2024-02-19 22:28:14
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 190 ms / 4,000 ms
コード長 11,873 bytes
コンパイル時間 4,335 ms
コンパイル使用メモリ 293,536 KB
実行使用メモリ 39,740 KB
最終ジャッジ日時 2024-09-29 03:35:25
合計ジャッジ時間 8,472 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// #pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
// #include <x86intrin.h>
using namespace std;
#if __cplusplus >= 202002L
using namespace numbers;
#endif
template<bool Enable_small_to_large = true>
struct disjoint_set{
int n, _group_count;
vector<int> p;
vector<list<int>> group;
disjoint_set(){ }
disjoint_set(int n): n(n), _group_count(n), p(n, -1), group(n){ assert(n >= 0);
for(auto i = 0; i < n; ++ i) group[i] = {i};
}
int make_set(){
p.push_back(-1);
group.push_back(list<int>{p});
++ _group_count;
return n ++;
}
int root(int u){
return p[u] < 0 ? u : p[u] = root(p[u]);
}
bool share(int a, int b){
return root(a) == root(b);
}
int size(int u){
return -p[root(u)];
}
bool merge(int u, int v){
u = root(u), v = root(v);
if(u == v) return false;
-- _group_count;
if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v);
p[u] += p[v], p[v] = u;
group[u].splice(group[u].end(), group[v]);
return true;
}
bool merge(int u, int v, auto act){
u = root(u), v = root(v);
if(u == v) return false;
-- _group_count;
bool swapped = false;
if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v), swapped = true;
p[u] += p[v], p[v] = u;
group[u].splice(group[u].end(), group[v]);
act(u, v, swapped);
return true;
}
int group_count() const{
return _group_count;
}
const list<int> &group_of(int u){
return group[root(u)];
}
vector<vector<int>> group_up(){
vector<vector<int>> g(n);
for(auto i = 0; i < n; ++ i) g[root(i)].push_back(i);
g.erase(remove_if(g.begin(), g.end(), [&](auto &s){ return s.empty(); }), g.end());
return g;
}
void clear(){
_group_count = n;
fill(p.begin(), p.end(), -1);
for(auto i = 0; i < n; ++ i) group[i] = {i};
}
friend ostream &operator<<(ostream &out, disjoint_set dsu){
auto gs = dsu.group_up();
out << "{";
if(!gs.empty()) for(auto i = 0; i < (int)gs.size(); ++ i){
out << "{";
for(auto j = 0; j < (int)gs[i].size(); ++ j){
out << gs[i][j];
if(j + 1 < (int)gs[i].size()) out << ", ";
}
out << "}";
if(i + 1 < (int)gs.size()) out << ", ";
}
return out << "}";
}
};
// Requires disjoint_set
template<class G>
vector<int> minimum_spanning_forest(const G &g){
vector<int> order(g.edge.size());
iota(order.begin(), order.end(), 0);
if(g.ignore) order.erase(remove_if(order.begin(), order.end(), [&](int id){ return g.ignore(id); }), order.end());
sort(order.begin(), order.end(), [&](int i, int j){ return g.edge[i].cost < g.edge[j].cost; });
disjoint_set dsu(g.n);
vector<int> res;
for(auto id: order){
auto &e = g.edge[id];
if(dsu.merge(e.from, e.to)) res.push_back(id);
}
return res;
}
template<class T>
vector<int> minimum_spanning_forest(int n, const vector<tuple<int, int, T>> &edge){
vector<int> order(edge.size());
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j){ return get<2>(edge[i]) < get<2>(edge[j]); });
disjoint_set dsu(n);
vector<int> res;
for(auto id: order){
auto &e = edge[id];
if(dsu.merge(get<0>(e), get<1>(e))) res.push_back(id);
}
return res;
}
template<class T>
struct graph{
using Weight_t = T;
struct Edge_t{
int from, to;
T cost;
};
int n;
vector<Edge_t> edge;
vector<vector<int>> adj;
function<bool(int)> ignore;
graph(int n = 1): n(n), adj(n){
assert(n >= 1);
}
graph(const vector<vector<int>> &adj, bool undirected = true): n((int)adj.size()), adj(n){
assert(n >= 1);
if(undirected){
for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) if(u < v) link(u, v);
}
else for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) orient(u, v);
}
graph(const vector<vector<pair<int, T>>> &adj, bool undirected = true): n((int)adj.size()), adj(n){
assert(n >= 1);
if(undirected){
for(auto u = 0; u < n; ++ u) for(auto [v, w]: adj[u]) if(u < v) link(u, v, w);
}
else for(auto u = 0; u < n; ++ u) for(auto [v, w]: adj[u]) orient(u, v, w);
}
graph(int n, vector<array<int, 2>> &edge, bool undirected = true): n(n), adj(n){
assert(n >= 1);
for(auto [u, v]: edge) undirected ? link(u, v) : orient(u, v);
}
graph(int n, vector<tuple<int, int, T>> &edge, bool undirected = true): n(n), adj(n){
assert(n >= 1);
for(auto [u, v, w]: edge) undirected ? link(u, v, w) : orient(u, v, w);
}
int operator()(int u, int id) const{
#ifdef LOCAL
assert(0 <= id && id < (int)edge.size());
assert(edge[id].from == u || edge[id].to == u);
#endif
return u ^ edge[id].from ^ edge[id].to;
}
int link(int u, int v, T w = {}){ // insert an undirected edge
int id = (int)edge.size();
adj[u].push_back(id), adj[v].push_back(id), edge.push_back({u, v, w});
return id;
}
int orient(int u, int v, T w = {}){ // insert a directed edge
int id = (int)edge.size();
adj[u].push_back(id), edge.push_back({u, v, w});
return id;
}
void clear(){
for(auto [u, v, w]: edge){
adj[u].clear();
adj[v].clear();
}
edge.clear();
ignore = {};
}
graph transposed() const{ // the transpose of the directed graph
graph res(n);
for(auto &e: edge) res.orient(e.to, e.from, e.cost);
res.ignore = ignore;
return res;
}
int degree(int u) const{ // the degree (outdegree if directed) of u (without the ignoration rule)
return (int)adj[u].size();
}
// The adjacency list is sorted for each vertex.
vector<vector<int>> get_adjacency_list() const{
vector<vector<int>> res(n);
for(auto u = 0; u < n; ++ u) for(auto id: adj[u]){
if(ignore && ignore(id)) continue;
res[(*this)(u, id)].push_back(u);
}
return res;
}
void set_ignoration_rule(const function<bool(int)> &f){
ignore = f;
}
void reset_ignoration_rule(){
ignore = nullptr;
}
friend ostream &operator<<(ostream &out, const graph &g){
for(auto id = 0; id < (int)g.edge.size(); ++ id){
if(g.ignore && g.ignore(id)) continue;
auto &e = g.edge[id];
out << "{" << e.from << ", " << e.to << ", " << e.cost << "}\n";
}
return out;
}
};
// Requires graph
struct heavy_light_decomposition{
int n;
vector<vector<int>> adj; // stores edge ids
vector<int> pv;
vector<int> pe;
vector<int> size;
vector<int> root_of;
vector<int> root;
vector<int> depth;
vector<int> next; // highest point of the heavy path
vector<int> prev; // lowest point of the heavy path
vector<int> pos;
vector<int> end;
vector<int> order;
vector<int> was;
void init(int n){
assert(n >= 1);
this->n = n;
adj.assign(n, {});
pv.assign(n, -1);
pe.assign(n, -1);
order.clear();
pos.assign(n, -1);
end.assign(n, -1);
size.assign(n, 1);
root_of.assign(n, -1);
root.clear();
depth.assign(n, -1);
next.assign(n, -1);
prev.assign(n, -1);
was.assign(n, -2);
attempt = -1;
}
int attempt;
template<class T>
void build(const graph<T> &g, const vector<int> &src){
assert(g.n <= n);
++ attempt;
root.clear(), order.clear();
for(auto id = 0; id < (int)g.edge.size(); ++ id){
if(g.ignore && g.ignore(id)) continue;
auto &e = g.edge[id];
adj[e.from].push_back(id), adj[e.to].push_back(id);
}
auto dfs_init = [&](auto self, int u)->void{
assert(was[u] != attempt); // CYCLE FOUND
was[u] = attempt;
prev[u] = u;
size[u] = 1;
if(root_of[u] != u){
adj[u].erase(find(adj[u].begin(), adj[u].end(), pe[u]));
}
for(auto &id: adj[u]){
int v = g(u, id);
pv[v] = u;
pe[v] = id;
depth[v] = depth[u] + 1;
root_of[v] = root_of[u];
next[v] = u;
self(self, v);
size[u] += size[v];
if(size[v] > size[g(u, adj[u][0])]) swap(id, adj[u][0]);
}
if(!adj[u].empty()) prev[u] = prev[g(u, adj[u][0])];
};
auto dfs_hld = [&](auto self, int u)->void{
pos[u] = (int)order.size();
order.push_back(u);
if(!adj[u].empty()){
int hv = g(u, adj[u][0]);
for(auto id: adj[u]){
int v = g(u, id);
next[v] = (v == hv ? next[u] : v);
self(self, v);
}
}
end[u] = (int)order.size();
};
for(auto r: src){
if(was[r] == attempt) continue;
pv[r] = pe[r] = -1;
depth[r] = 0;
root_of[r] = r;
root.push_back(r);
next[r] = r;
dfs_init(dfs_init, r);
dfs_hld(dfs_hld, r);
}
}
// Check if u is visited during the last build call
bool visited(int u) const{
assert(0 <= u && u < n);
return was[u] == attempt;
}
// O(1)
bool ancestor_of(int u, int v) const{
return pos[u] <= pos[v] && end[v] <= end[u];
}
int lca(int u, int v) const{
for(; next[u] != next[v]; v = pv[next[v]]) if(depth[next[u]] > depth[next[v]]) swap(u, v);
return depth[u] < depth[v] ? u : v;
}
int steps(int u, int v, int w = -1) const{
return depth[u] + depth[v] - 2 * depth[~w ? w : lca(u, v)];
}
// f reads the position in the data structure
// One application of f
void access_node(int u, auto f) const{
f(pos[u]);
}
// One application of f
template<int VALS_IN_EDGES = 0>
void access_subtree(int u, auto f) const{
f(pos[u] + VALS_IN_EDGES, end[u]);
}
// f(left, right, (left->right ?))
// O(log(n)) applications of f
template<int VALS_IN_EDGES = 0>
void access_path(int u, int v, auto f) const{
bool dir = true;
for(; next[u] != next[v]; v = pv[next[v]]){
if(depth[next[u]] > depth[next[v]]) swap(u, v), dir = !dir;
f(pos[next[v]], pos[v] + 1, dir);
}
if(depth[u] > depth[v]) swap(u, v), dir = !dir;
f(pos[u] + VALS_IN_EDGES, pos[v] + 1, dir);
}
// Pair of indices {l, r} in the data structure. resr is reversed(v->next[v], pv[next[v]]-> ...)
// O(log(n))
auto get_path(int u, int v) const{
vector<pair<int, int>> resl, resr;
access_path(u, v, [&](int l, int r, bool dir){ (dir ? resl : resr).push_back({l, r}); });
return pair{resl, resr};
}
};
// Specialization of sparse_table
// Range min query by default. Set cmp = greater for max query
template<class T, class Compare = less<>>
struct range_minmax_query_solver{
int n;
vector<vector<T>> data;
Compare cmp;
T T_id;
range_minmax_query_solver(){ }
// O(n * log(n))
range_minmax_query_solver(const vector<T> &a, Compare cmp = less<>(), T T_id = numeric_limits<T>::max()): n((int)a.size()), cmp(cmp), T_id(T_id),
        data({a}){
for(auto p = 1, i = 1; p << 1 <= n; p <<= 1, ++ i){
data.emplace_back(n - (p << 1) + 1);
for(auto j = 0; j < (int)data[i].size(); ++ j) data[i][j] = cmp(data[i - 1][j], data[i - 1][j + p]) ? data[i - 1][j] : data[i - 1][j + p]
                ;
}
}
// O(1)
T query(int l, int r) const{
assert(0 <= l && l <= r && r <= n);
if(l == r) return T_id;
int d = __lg(r - l);
return cmp(data[d][l], data[d][r - (1 << d)]) ? data[d][l] : data[d][r - (1 << d)];
}
};
int main(){
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(ios::badbit | ios::failbit);
int n, m;
long long th;
cin >> n >> m >> th;
vector<tuple<int, int, int>> edge(m);
vector<int> profit(m);
for(auto i = 0; i < m; ++ i){
auto &[u, v, w] = edge[i];
cin >> u >> v >> w >> profit[i], -- u, -- v;
}
auto mst = minimum_spanning_forest(n, edge);
long long mst_cost = 0;
vector<int> on_mst(m);
int res = 0;
graph<int> g(n);
for(auto id: mst){
mst_cost += get<2>(edge[id]);
on_mst[id] = true;
res = max(res, profit[id]);
auto [u, v, w] = edge[id];
g.link(u, v, w);
}
if(mst_cost > th){
cout << "-1\n";
return 0;
}
heavy_light_decomposition hld;
hld.init(n);
hld.build(g, {0});
vector<int> init(n);
for(auto i = 1; i < n; ++ i){
init[i] = g.edge[hld.pe[hld.order[i]]].cost;
}
range_minmax_query_solver rmaxq(init, greater<>(), numeric_limits<int>::min());
vector<int> order(m);
iota(order.begin(), order.end(), 0);
ranges::sort(order, [&](int i, int j){ return profit[i] > profit[j]; });
for(auto i: order){
if(on_mst[i] || profit[i] < res){
continue;
}
auto [u, v, w] = edge[i];
int maxv = 0;
hld.access_path<true>(u, v, [&](int l, int r, bool){ maxv = max(maxv, rmaxq.query(l, r)); });
if(mst_cost + get<2>(edge[i]) - maxv <= th){
cout << profit[i] << "\n";
return 0;
}
}
cout << res << "\n";
return 0;
}
/*
*/
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0