test/aoj/challenge/2559.2.test.cpp

• View this file on GitHub
• Last update: 2025-06-10 13:56:45+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/2559

Depends on

• 重み付きグラフ (lib/graph/graph.hpp)
• leftist heap (lib/heap/leftist_heap.hpp)
• 素集合データ構造 (lib/tree/union_find.hpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2559
#include <algorithm>
#include <cstdint>
#include <functional>
#include <iostream>
#include <numeric>
#include <tuple>
#include <utility>
#include <vector>
#include "graph/graph.hpp"
#include "heap/leftist_heap.hpp"
#include "tree/union_find.hpp"

int main(void) {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::tuple<int, int, int>> edges(m);
    for (auto &[u, v, w] : edges) std::cin >> u >> v >> w, --u, --v;
    std::vector<int> ord(m);
    std::iota(ord.begin(), ord.end(), 0);
    std::sort(ord.begin(), ord.end(),
              [&](int x, int y) { return std::get<2>(edges[x]) < std::get<2>(edges[y]); });
    std::int64_t sum = 0;
    union_find uf(n);
    std::vector<leftist_heap<std::pair<int, int>, std::greater<>>> heap(n);
    Graph<int> g(n);
    std::vector<bool> used(m);
    for (auto x : ord) {
        auto [u, v, w] = edges[x];
        if (uf.same(u, v)) {
            heap[u].emplace(w, v);
            heap[v].emplace(w, u);
        } else {
            sum += w;
            uf.unite(u, v);
            g.add_edges(u, v, x);
            used[x] = true;
        }
    }
    if (uf.size(0) != n) {
        for (int i = 0; i < m; ++i) std::cout << -1 << '\n';
        return 0;
    }
    std::vector<std::int64_t> ans(m, -1);
    for (int i = 0; i < m; ++i) {
        if (!used[i]) ans[i] = sum;
    }
    uf = union_find(n);
    auto dfs = [&](auto self, int x, int p) -> void {
        for (auto e : g[x]) {
            if (e.to() == p) continue;
            self(self, e.to(), x);
            while (!heap[e.to()].empty() && uf.same(e.to(), heap[e.to()].top().second))
                heap[e.to()].pop();
            if (!heap[e.to()].empty()) {
                auto [u, v, w] = edges[e.weight()];
                ans[e.weight()] = sum - w + heap[e.to()].top().first;
            }
            heap[x].meld(heap[e.to()]);
            uf.unite(x, e.to());
        }
    };
    dfs(dfs, 0, -1);
    for (int i = 0; i < m; ++i) std::cout << ans[i] << '\n';

    return 0;
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/resolver.py", line 291, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 242, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 479, in update
    self._resolve(pathlib.Path(included), included_from=path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 286, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: graph/graph.hpp: line -1: no such header

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00	AC	3 ms	4 MB
g++	00_sample_01	AC	2 ms	3 MB
g++	00_sample_02	AC	2 ms	3 MB
g++	00_sample_03	AC	2 ms	3 MB
g++	10_random_0_00	AC	2 ms	4 MB
g++	10_random_0_01	AC	2 ms	3 MB
g++	10_random_0_02	AC	2 ms	4 MB
g++	10_random_0_03	AC	2 ms	4 MB
g++	10_random_0_04	AC	2 ms	3 MB
g++	10_random_0_05	AC	2 ms	4 MB
g++	10_random_0_06	AC	2 ms	4 MB
g++	10_random_0_07	AC	2 ms	3 MB
g++	10_random_0_08	AC	2 ms	3 MB
g++	10_random_0_09	AC	2 ms	4 MB
g++	10_random_1_00	AC	4 ms	4 MB
g++	10_random_1_01	AC	5 ms	4 MB
g++	10_random_1_02	AC	2 ms	3 MB
g++	10_random_1_03	AC	4 ms	4 MB
g++	10_random_1_04	AC	4 ms	4 MB
g++	10_random_1_05	AC	3 ms	4 MB
g++	10_random_1_06	AC	3 ms	4 MB
g++	10_random_1_07	AC	3 ms	4 MB
g++	10_random_1_08	AC	9 ms	4 MB
g++	10_random_1_09	AC	8 ms	4 MB
g++	10_random_2_00	AC	237 ms	25 MB
g++	10_random_2_01	AC	189 ms	23 MB
g++	10_random_2_02	AC	220 ms	25 MB
g++	20_minimum	AC	3 ms	4 MB
g++	30_corner_00	AC	2 ms	4 MB
g++	30_star	AC	13 ms	5 MB
g++	31_perfect	AC	40 ms	8 MB
g++	32_zero	AC	3 ms	4 MB
g++	33_ring	AC	7 ms	5 MB
g++	40_isolated	AC	2 ms	3 MB
g++	41_tree	AC	4 ms	4 MB
g++	90_antidfs	AC	148 ms	47 MB
g++	91_antiRecHeap	AC	194 ms	46 MB

Back to top page