cp-documentation

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

View the Project on GitHub zawa-tin/cp-documentation

:heavy_check_mark: Test/CF/CF1026-E.test.cpp

Depends on

Code

// #define PROBLEM "https://codeforces.com/contest/2110/problem/E"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#include "../../Src/Sequence/CompressedSequence.hpp"
#include "../../Src/Graph/EulerianTrail.hpp"
using namespace zawa;

#include <iostream>
#include <utility>
#include <vector>

void solve() {
    int N;
    std::cin >> N;
    std::vector<std::pair<int, int>> E(N);
    std::vector<int> app;
    for (auto& [u, v] : E) {
        std::cin >> u >> v;
        app.push_back(u);
        app.push_back(v);
    }
    CompressedSequence comp{app};
    std::vector<std::pair<int, int>> edge(N);
    for (int i = 0 ; i < N ; i++) {
        edge[i].first = comp[E[i].first];
        edge[i].second = comp.size() + comp[E[i].second];
    }
    auto ans = EulerianTrail(2 * comp.size(), edge, false);
    if (ans) {
        std::cout << "YES\n";
        auto es = std::move(ans->second);
        for (int i = 0 ; i < N ; i++) std::cout << es[i] + 1 << (i + 1 == N ? '\n' : ' ');
    }
    else {
        std::cout << "NO\n";
    }
}

int main() {
#ifdef ONLINE_JUDGE
    int T;
    std::cin >> T;
    while (T--) solve();
#else
    std::cout << "Hello World\n";
#endif
}
#line 1 "Test/CF/CF1026-E.test.cpp"
// #define PROBLEM "https://codeforces.com/contest/2110/problem/E"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#line 2 "Src/Sequence/CompressedSequence.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Sequence/CompressedSequence.hpp"

#include <vector>
#include <algorithm>
#include <cassert>
#include <iterator>
#include <limits>

namespace zawa {

template <class T>
class CompressedSequence {
public:

    static constexpr u32 NotFound = std::numeric_limits<u32>::max();

    CompressedSequence() = default;

    template <class InputIterator>
    CompressedSequence(InputIterator first, InputIterator last) : comped_(first, last), f_{} {
        std::sort(comped_.begin(), comped_.end());
        comped_.erase(std::unique(comped_.begin(), comped_.end()), comped_.end());
        comped_.shrink_to_fit();
        f_.reserve(std::distance(first, last));
        for (auto it{first} ; it != last ; it++) {
            f_.emplace_back(std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), *it)));
        }
    }

    CompressedSequence(const std::vector<T>& A) : CompressedSequence(A.begin(), A.end()) {}

    inline usize size() const noexcept {
        return comped_.size();
    }

    u32 operator[](const T& v) const {
        return std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
    }

    u32 upper_bound(const T& v) const {
        return std::distance(comped_.begin(), std::upper_bound(comped_.begin(), comped_.end(), v));
    }

    u32 find(const T& v) const {
        u32 i = std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
        return i == comped_.size() or comped_[i] != v ? NotFound : i;
    }

    bool contains(const T& v) const {
        u32 i = std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
        return i < comped_.size() and comped_[i] == v;
    }

    u32 at(const T& v) const {
        u32 res = find(v);
        assert(res != NotFound);
        return res;
    }

    inline u32 map(u32 i) const noexcept {
        assert(i < f_.size());
        return f_[i];
    }

    inline T inverse(u32 i) const noexcept {
        assert(i < size());
        return comped_[i];
    }

    inline std::vector<T> comped() const noexcept {
        return comped_;
    }

private:

    std::vector<T> comped_;

    std::vector<u32> f_;

};

} // namespace zawa
#line 2 "Src/Graph/EulerianTrail.hpp"

#line 5 "Src/Graph/EulerianTrail.hpp"
#include <optional>
#include <utility>
#line 8 "Src/Graph/EulerianTrail.hpp"

#line 10 "Src/Graph/EulerianTrail.hpp"

namespace zawa {

// first: 頂点列, second: 辺番号列
template <class T>
std::optional<std::pair<std::vector<T>, std::vector<usize>>> EulerianTrail(usize n, const std::vector<std::pair<T, T>>& edges, bool directed) {
    std::vector<std::vector<std::pair<T, usize>>> g(n);
    for (usize i = 0 ; auto [u, v] : edges) {
        assert(u < n);
        assert(v < n);
        g[u].push_back({v, i});
        if (!directed) g[v].push_back({u, i});
        i++;
    }
    std::vector<bool> used(edges.size());
    std::vector<usize> cur(n), es;
    std::vector<T> vs;
    es.reserve(edges.size());
    vs.reserve(edges.size() + 1);
    auto dfs = [&](auto dfs, const T v) -> void {
        while (cur[v] < g[v].size()) {
            auto [x, i] = g[v][cur[v]++];
            if (!used[i]) {
                used[i] = true;
                dfs(dfs, x);
                es.push_back(i);
                vs.push_back(v);
            }
        }
    };
    usize st = edges.size() ? edges[0].first : 0, go = st;
    if (directed) {
        std::vector<usize> deg(n);
        for (auto [u, v] : edges) {
            deg[u]++;
            deg[v]--;
        }
        const usize p1 = 1, m1 = static_cast<usize>(-1);
        bool fnst = false, fngo = false;
        for (usize i = 0 ; i < n ; i++) {
            if (deg[i] == p1) {
                if (fnst) return std::nullopt;
                fnst = true;
                st = i;
            }
            else if (deg[i] == m1) {
                if (fngo) return std::nullopt;
                fngo = true;
                go = i;
            }
            else if (deg[i]) return std::nullopt;
        }
    }
    else {
        usize cntOdd = 0;
        for (usize i = 0 ; i < n ; i++) if (g[i].size() & 1) {
            if (cntOdd++) go = i;
            else st = i;
        }
        if (cntOdd != 0 and cntOdd != 2) return std::nullopt;
    }
    if (n) {
        dfs(dfs, st);
        std::ranges::reverse(vs);
        vs.push_back(go);
        std::ranges::reverse(es);
    }
    if (edges.size() != es.size()) return std::nullopt;
    return std::make_pair(vs, es);
}

} // namespace zawa
#line 6 "Test/CF/CF1026-E.test.cpp"
using namespace zawa;

#include <iostream>
#line 11 "Test/CF/CF1026-E.test.cpp"

void solve() {
    int N;
    std::cin >> N;
    std::vector<std::pair<int, int>> E(N);
    std::vector<int> app;
    for (auto& [u, v] : E) {
        std::cin >> u >> v;
        app.push_back(u);
        app.push_back(v);
    }
    CompressedSequence comp{app};
    std::vector<std::pair<int, int>> edge(N);
    for (int i = 0 ; i < N ; i++) {
        edge[i].first = comp[E[i].first];
        edge[i].second = comp.size() + comp[E[i].second];
    }
    auto ans = EulerianTrail(2 * comp.size(), edge, false);
    if (ans) {
        std::cout << "YES\n";
        auto es = std::move(ans->second);
        for (int i = 0 ; i < N ; i++) std::cout << es[i] + 1 << (i + 1 == N ? '\n' : ' ');
    }
    else {
        std::cout << "NO\n";
    }
}

int main() {
#ifdef ONLINE_JUDGE
    int T;
    std::cin >> T;
    while (T--) solve();
#else
    std::cout << "Hello World\n";
#endif
}
Back to top page