結果
問題 | No.2642 Don't cut line! |
ユーザー |
👑 ![]() |
提出日時 | 2024-02-19 22:03:48 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 7,377 bytes |
コンパイル時間 | 3,968 ms |
コンパイル使用メモリ | 281,128 KB |
実行使用メモリ | 47,068 KB |
最終ジャッジ日時 | 2024-09-29 03:32:21 |
合計ジャッジ時間 | 6,776 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 WA * 1 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define FOR(i,m,n) for(int i=(m);i<(n);++i)#define REP(i,n) FOR(i,0,n)using ll = long long;constexpr int INF = 0x3f3f3f3f;constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;constexpr double EPS = 1e-8;constexpr int MOD = 998244353;// constexpr int MOD = 1000000007;constexpr int DY4[]{1, 0, -1, 0}, DX4[]{0, -1, 0, 1};constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1};constexpr int DX8[]{0, -1, -1, -1, 0, 1, 1, 1};template <typename T, typename U>inline bool chmax(T& a, U b) { return a < b ? (a = b, true) : false; }template <typename T, typename U>inline bool chmin(T& a, U b) { return a > b ? (a = b, true) : false; }struct IOSetup {IOSetup() {std::cin.tie(nullptr);std::ios_base::sync_with_stdio(false);std::cout << fixed << setprecision(20);}} iosetup;template <typename CostType>struct Edge {CostType cost;int src, dst;explicit Edge(const int src, const int dst, const CostType cost = 0): cost(cost), src(src), dst(dst) {}auto operator<=>(const Edge& x) const = default;};struct UnionFind {explicit UnionFind(const int n) : data(n, -1) {}int root(const int ver) {return data[ver] < 0 ? ver : data[ver] = root(data[ver]);}bool unite(int u, int v) {u = root(u);v = root(v);if (u == v) return false;if (data[u] > data[v]) std::swap(u, v);data[u] += data[v];data[v] = u;return true;}bool is_same(const int u, const int v) { return root(u) == root(v); }int size(const int ver) { return -data[root(ver)]; }private:std::vector<int> data;};template <typename CostType>struct HeavyLightDecomposition {std::vector<int> parent, subtree, id, inv, head;std::vector<CostType> cost;explicit HeavyLightDecomposition(const std::vector<std::vector<Edge<CostType>>>& graph,const int root = 0): graph(graph) {const int n = graph.size();parent.assign(n, -1);subtree.assign(n, 1);dfs1(root);id.resize(n);inv.resize(n);head.assign(n, root);int cur_id = 0;dfs2(root, &cur_id);}template <typename Fn>void update_v(int u, int v, const Fn f) const {while (true) {if (id[u] > id[v]) std::swap(u, v);f(std::max(id[head[v]], id[u]), id[v] + 1);if (head[u] == head[v]) break;v = parent[head[v]];}}template <typename F, typename G, typename T>T query_v(int u, int v, const F f, const G g, const T id_t) const {T left = id_t, right = id_t;while (true) {if (id_t[u] > id_t[v]) {std::swap(u, v);std::swap(left, right);}left = g(left, f(std::max(id_t[head[v]], id_t[u]), id_t[v] + 1));if (head[u] == head[v]) break;v = parent[head[v]];}return g(left, right);}template <typename Fn>void update_subtree_v(const int ver, const Fn f) const {f(id[ver], id[ver] + subtree[ver]);}template <typename T, typename Fn>T query_subtree_v(const int ver, const Fn f) const {return f(id[ver], id[ver] + subtree[ver]);}template <typename Fn>void update_e(int u, int v, const Fn f) const {while (true) {if (id[u] > id[v]) std::swap(u, v);if (head[u] == head[v]) {f(id[u], id[v]);break;} else {f(id[head[v]] - 1, id[v]);v = parent[head[v]];}}}template <typename F, typename G, typename T>T query_e(int u, int v, const F f, const G g, const T id_t) const {T left = id_t, right = id_t;while (true) {if (id[u] > id[v]) {std::swap(u, v);std::swap(left, right);}if (head[u] == head[v]) {left = g(left, f(id[u], id[v]));break;} else {left = g(left, f(id[head[v]] - 1, id[v]));v = parent[head[v]];}}return g(left, right);}template <typename Fn>void update_subtree_e(const int ver, const Fn f) const {f(id[ver], id[ver] + subtree[ver] - 1);}template <typename T, typename Fn>T query_subtree_e(const int ver, const Fn f) const {return f(id[ver], id[ver] + subtree[ver] - 1);}int lowest_common_ancestor(int u, int v) const {while (true) {if (id[u] > id[v]) std::swap(u, v);if (head[u] == head[v]) break;v = parent[head[v]];}return u;}private:std::vector<std::vector<Edge<CostType>>> graph;void dfs1(const int ver) {for (int i = 0; std::cmp_less(i, graph[ver].size()); ++i) {Edge<CostType>& e = graph[ver][i];if (e.dst != parent[ver]) {parent[e.dst] = ver;dfs1(e.dst);subtree[ver] += subtree[e.dst];if (subtree[e.dst] > subtree[graph[ver].front().dst]) {std::swap(e, graph[ver].front());}}}}void dfs2(const int ver, int* cur_id) {id[ver] = (*cur_id)++;inv[id[ver]] = ver;for (const Edge<CostType>& e : graph[ver]) {if (e.dst != parent[ver]) {head[e.dst] = (e.dst == graph[ver].front().dst ? head[ver] : e.dst);cost.emplace_back(e.cost);dfs2(e.dst, cur_id);}}}};template <typename Band>struct SparseTable {using BinOp = std::function<Band(Band, Band)>;SparseTable() = default;explicit SparseTable(const std::vector<Band>& a, const BinOp bin_op) {init(a, bin_op);}void init(const std::vector<Band>& a, const BinOp bin_op_) {bin_op = bin_op_;const int n = a.size();assert(n > 0);lg.assign(n + 1, 0);for (int i = 2; i <= n; ++i) {lg[i] = lg[i >> 1] + 1;}const int table_h = std::countr_zero(std::bit_floor(a.size())) + 1;data.assign(table_h, std::vector<Band>(n));std::copy(a.begin(), a.end(), data.front().begin());for (int i = 1; i < table_h; ++i) {for (int j = 0; j + (1 << i) <= n; ++j) {data[i][j] = bin_op(data[i - 1][j], data[i - 1][j + (1 << (i - 1))]);}}}Band query(const int left, const int right) const {assert(left < right);const int h = lg[right - left];return bin_op(data[h][left], data[h][right - (1 << h)]);}private:BinOp bin_op;std::vector<int> lg;std::vector<std::vector<Band>> data;};int main() {int n, k; ll c; cin >> n >> k >> 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<int> order(k);iota(order.begin(), order.end(), 0);ranges::sort(order, {}, [&](const int i) -> int { return w[i]; });vector<int> is_used(k, false);vector<vector<Edge<ll>>> tree(n);UnionFind union_find(n);ll cost = 0;for (const int i : order) {if (union_find.unite(u[i], v[i])) {is_used[i] = true;tree[u[i]].emplace_back(u[i], v[i], w[i]);tree[v[i]].emplace_back(v[i], u[i], w[i]);cost += w[i];}}if (cost > c) {cout << "-1\n";return 0;}const HeavyLightDecomposition hld(tree);const SparseTable<ll> table(hld.cost, [](const ll a, const ll b) { return min(a, b); });int ans = 0;REP(i, k) {if (is_used[i] || cost - hld.query_e(u[i], v[i], [&](const int l, const int r) -> ll { return l == r ? LINF : table.query(l, r); }, [](const ll x, const ll y) -> ll { return min(x, y); }, LINF) + w[i] <= c) {chmax(ans, p[i]);}}cout << ans << '\n';return 0;}