#952742 (C++23) No.2642 Don't cut line!

提出ソース

結果

問題	No.2642 Don't cut line!
ユーザー	👑 emthrm
提出日時	2024-02-19 22:03:48
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	WA (最新) AC (最初)
実行時間	-
コード長	7,377 bytes
コンパイル時間	4,087 ms
コンパイル使用メモリ	280,396 KB
実行使用メモリ	47,192 KB
最終ジャッジ日時	2024-02-20 12:46:44
合計ジャッジ時間	8,192 ms
ジャッジサーバーID （参考情報）	judge12 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	WA	-
testcase_01	AC	146 ms 46,616 KB
testcase_02	AC	146 ms 47,192 KB
testcase_03	AC	146 ms 43,872 KB
testcase_04	AC	143 ms 43,652 KB
testcase_05	AC	147 ms 45,084 KB
testcase_06	AC	49 ms 6,676 KB
testcase_07	AC	49 ms 6,676 KB
testcase_08	AC	48 ms 6,676 KB
testcase_09	AC	48 ms 6,676 KB
testcase_10	AC	50 ms 6,676 KB
testcase_11	AC	50 ms 6,676 KB
testcase_12	AC	52 ms 6,676 KB
testcase_13	AC	48 ms 6,676 KB
testcase_14	AC	49 ms 6,676 KB
testcase_15	AC	52 ms 6,676 KB
testcase_16	AC	87 ms 13,696 KB
testcase_17	AC	121 ms 39,212 KB
testcase_18	AC	135 ms 40,392 KB
testcase_19	AC	89 ms 31,504 KB
testcase_20	AC	54 ms 15,232 KB
testcase_21	AC	42 ms 6,676 KB
testcase_22	AC	58 ms 11,008 KB
testcase_23	AC	150 ms 44,192 KB
testcase_24	AC	65 ms 19,396 KB
testcase_25	AC	65 ms 17,540 KB
testcase_26	AC	60 ms 9,728 KB
testcase_27	AC	94 ms 30,296 KB
testcase_28	AC	132 ms 40,880 KB
testcase_29	AC	60 ms 12,032 KB
testcase_30	AC	60 ms 15,792 KB
testcase_31	AC	107 ms 34,664 KB
testcase_32	AC	58 ms 14,336 KB
testcase_33	AC	2 ms 6,676 KB
testcase_34	AC	2 ms 6,676 KB
testcase_35	AC	2 ms 6,676 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード