結果
問題 | No.2642 Don't cut line! |
ユーザー |
|
提出日時 | 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 |
ソースコード
// #pragma GCC optimize("O3,unroll-loops")#include <bits/stdc++.h>// #include <x86intrin.h>using namespace std;#if __cplusplus >= 202002Lusing namespace numbers;#endiftemplate<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_settemplate<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 LOCALassert(0 <= id && id < (int)edge.size());assert(edge[id].from == u || edge[id].to == u);#endifreturn u ^ edge[id].from ^ edge[id].to;}int link(int u, int v, T w = {}){ // insert an undirected edgeint 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 edgeint 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 graphgraph 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 graphstruct heavy_light_decomposition{int n;vector<vector<int>> adj; // stores edge idsvector<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 pathvector<int> prev; // lowest point of the heavy pathvector<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 FOUNDwas[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 callbool 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 fvoid access_node(int u, auto f) const{f(pos[u]);}// One application of ftemplate<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 ftemplate<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 querytemplate<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;}/**/