library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub gyouzasushi/library

:heavy_check_mark: test/unit/tree_diameter.test.cpp

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <vector>

#include "graph/tree_diameter.hpp"
int main() {
    std::mt19937 rng(20261028);
    for (int trial = 0; trial < 300; trial++) {
        int n = 1 + rng() % 12;
        bool weighted = trial % 2;
        std::vector<std::vector<std::pair<int, long long>>> g(n);
        tree_diameter<long long> d(n);
        for (int v = 1; v < n; v++) {
            int p = rng() % v;
            long long w = weighted ? rng() % 5 : 1;
            g[v].emplace_back(p, w);
            g[p].emplace_back(v, w);
            d.add_edge(p, v, w);
        }
        d.build();
        std::vector<std::vector<long long>> dist(n, std::vector<long long>(n, -1));
        for (int s = 0; s < n; s++) {
            std::vector<int> st = {s};
            dist[s][s] = 0;
            while (!st.empty()) {
                int x = st.back();
                st.pop_back();
                for (auto [y, w] : g[x]) {
                    if (dist[s][y] != -1) continue;
                    dist[s][y] = dist[s][x] + w;
                    st.push_back(y);
                }
            }
        }
        long long diam = 0;
        for (int s = 0; s < n; s++) diam = std::max(diam, *std::max_element(dist[s].begin(), dist[s].end()));
        assert(d.length() == diam);
        auto [u, v] = d.ends();
        assert(dist[u][v] == diam);
        const std::vector<int>& path = d.path();
        assert(path.front() == u && path.back() == v);
        long long len = 0;
        for (int i = 0; i + 1 < int(path.size()); i++) {
            bool found = false;
            for (auto [y, w] : g[path[i]]) {
                if (y == path[i + 1]) found = true, len += w;
            }
            assert(found);
        }
        assert(len == diam);
        auto [a, b] = d.center();
        std::vector<long long> ecc(n);
        for (int s = 0; s < n; s++) ecc[s] = *std::max_element(dist[s].begin(), dist[s].end());
        if (a == b) {
            assert(0 <= a && a < n);
            assert(2 * ecc[a] == diam);
        } else {
            long long w = -1;
            for (auto [y, ww] : g[a]) {
                if (y == b) w = ww;
            }
            assert(w > 0);
            double t = diam / 2.0 - dist[u][a];
            assert(0 < t && t < w);
            double e = 0;
            for (int x = 0; x < n; x++) e = std::max(e, std::min(dist[a][x] + t, dist[b][x] + w - t));
            assert(e == diam / 2.0);
        }
    }
    std::cout << "Hello World" << std::endl;
    return 0;
}
#line 1 "test/unit/tree_diameter.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <vector>

#line 4 "graph/tree_diameter.hpp"
#include <utility>
#line 6 "graph/tree_diameter.hpp"
template <class T>
struct tree_diameter {
public:
    tree_diameter() : tree_diameter(0) {
    }
    explicit tree_diameter(int n) : _n(n), g(n) {
    }
    void add_edge(int u, int v, T w = 1) {
        assert(0 <= u && u < _n);
        assert(0 <= v && v < _n);
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    void build() {
        assert(_n >= 1);
        std::vector<int> par;
        std::vector<T> d;
        search(0, d, par);
        _u = int(std::ranges::max_element(d) - d.begin());
        search(_u, d, par);
        _v = int(std::ranges::max_element(d) - d.begin());
        _length = d[_v];
        _path.clear();
        for (int x = _v; x != -1; x = par[x]) _path.push_back(x);
        std::ranges::reverse(_path);
        for (int i = 0;; i++) {
            T pos = d[_path[i]];
            if (pos == _length - pos) {
                _center = {_path[i], _path[i]};
                break;
            }
            if (pos > _length - pos) {
                _center = {_path[i - 1], _path[i]};
                break;
            }
        }
    }
    T length() const {
        return _length;
    }
    std::pair<int, int> ends() const {
        return {_u, _v};
    }
    const std::vector<int>& path() const {
        return _path;
    }
    std::pair<int, int> center() const {
        return _center;
    }

private:
    int _n, _u = -1, _v = -1;
    std::pair<int, int> _center = {-1, -1};
    T _length = T(0);
    std::vector<std::vector<std::pair<int, T>>> g;
    std::vector<int> _path;
    void search(int s, std::vector<T>& d, std::vector<int>& par) const {
        d.assign(_n, T(0));
        par.assign(_n, -1);
        std::vector<int> st = {s};
        par[s] = s;
        while (!st.empty()) {
            int x = st.back();
            st.pop_back();
            for (auto [y, w] : g[x]) {
                if (par[y] != -1) continue;
                par[y] = x;
                d[y] = d[x] + w;
                st.push_back(y);
            }
        }
        par[s] = -1;
    }
};
#line 9 "test/unit/tree_diameter.test.cpp"
int main() {
    std::mt19937 rng(20261028);
    for (int trial = 0; trial < 300; trial++) {
        int n = 1 + rng() % 12;
        bool weighted = trial % 2;
        std::vector<std::vector<std::pair<int, long long>>> g(n);
        tree_diameter<long long> d(n);
        for (int v = 1; v < n; v++) {
            int p = rng() % v;
            long long w = weighted ? rng() % 5 : 1;
            g[v].emplace_back(p, w);
            g[p].emplace_back(v, w);
            d.add_edge(p, v, w);
        }
        d.build();
        std::vector<std::vector<long long>> dist(n, std::vector<long long>(n, -1));
        for (int s = 0; s < n; s++) {
            std::vector<int> st = {s};
            dist[s][s] = 0;
            while (!st.empty()) {
                int x = st.back();
                st.pop_back();
                for (auto [y, w] : g[x]) {
                    if (dist[s][y] != -1) continue;
                    dist[s][y] = dist[s][x] + w;
                    st.push_back(y);
                }
            }
        }
        long long diam = 0;
        for (int s = 0; s < n; s++) diam = std::max(diam, *std::max_element(dist[s].begin(), dist[s].end()));
        assert(d.length() == diam);
        auto [u, v] = d.ends();
        assert(dist[u][v] == diam);
        const std::vector<int>& path = d.path();
        assert(path.front() == u && path.back() == v);
        long long len = 0;
        for (int i = 0; i + 1 < int(path.size()); i++) {
            bool found = false;
            for (auto [y, w] : g[path[i]]) {
                if (y == path[i + 1]) found = true, len += w;
            }
            assert(found);
        }
        assert(len == diam);
        auto [a, b] = d.center();
        std::vector<long long> ecc(n);
        for (int s = 0; s < n; s++) ecc[s] = *std::max_element(dist[s].begin(), dist[s].end());
        if (a == b) {
            assert(0 <= a && a < n);
            assert(2 * ecc[a] == diam);
        } else {
            long long w = -1;
            for (auto [y, ww] : g[a]) {
                if (y == b) w = ww;
            }
            assert(w > 0);
            double t = diam / 2.0 - dist[u][a];
            assert(0 < t && t < w);
            double e = 0;
            for (int x = 0; x < n; x++) e = std::max(e, std::min(dist[a][x] + t, dist[b][x] + w - t));
            assert(e == diam / 2.0);
        }
    }
    std::cout << "Hello World" << std::endl;
    return 0;
}
Back to top page