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/Manual/abc271_d.test.cpp

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#include "../../Src/Template/IOSetting.hpp"
#include "../../Src/Graph/ShortestPath/BFS.hpp"

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

/*
 * ABC271-D Flip and Adjust
 * https://atcoder.jp/contests/abc271/submissions/48494158
 */

void solve() {
    using namespace zawa; 
    SetFastIO();
    int n, s; std::cin >> n >> s;
    
    auto f{[&](int card, int sum) -> int {
        return card * (s + 1) + sum;
    }};

    BFS bfs((n + 1) * (s + 1));
    for (int i{} ; i < n ; i++) {
        int a, b; std::cin >> a >> b;
        for (int j{} ; j + a <= s ; j++) {
            bfs.addDirectedEdge(f(i, j), f(i + 1, j + a), 0);
        }
        for (int j{} ; j + b <= s ; j++) {
            bfs.addDirectedEdge(f(i, j), f(i + 1, j + b), 1);
        }
    }

    auto tree{bfs.build(f(0, 0))};
    if (tree.connect(f(n, s))) {
        std::cout << "Yes\n";
        for (const auto& e : tree.pathE(f(n, s))) {
            std::cout << (e.id ? 'T' : 'H');
        }
        std::cout << '\n';
    }
    else {
        std::cout << "No" << '\n';
    }
}

int main() {
#ifdef ATCODER
    solve();
#else
    std::cout << "Hello World" << '\n';
#endif
}
#line 1 "Test/Manual/abc271_d.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#line 2 "Src/Template/IOSetting.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/Template/IOSetting.hpp"

#include <iostream>
#include <iomanip>

namespace zawa {

void SetFastIO() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
}

void SetPrecision(u32 dig) {
    std::cout << std::fixed << std::setprecision(dig);
}

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

#line 2 "Src/Graph/ShortestPath/ShortestPathTree.hpp"

#line 2 "Src/Graph/ShortestPath/Edge.hpp"

#line 4 "Src/Graph/ShortestPath/Edge.hpp"

namespace zawa {

namespace internal {

class Edge {
protected:
    static constexpr u32 INVALID{static_cast<u32>(-1)};
public:
    u32 parent{INVALID}; 
    u32 id{INVALID};
    Edge() = default;
    Edge(u32 parent, u32 id) : parent{parent}, id{id} {}
    Edge& operator=(const Edge& edge) {
        parent = edge.parent;
        id = edge.id;
        return *this;
    }
    inline bool exist() const noexcept {
        return parent != INVALID;
    }
    static constexpr u32 invalid() noexcept {
        return INVALID; 
    }
};

template <class Weight>
class WeightedEdge : public Edge {
public:
    Weight weight{INVALID};
    WeightedEdge() = default;
    WeightedEdge(u32 parent, const Weight& weight, u32 id)
        : Edge{parent, id}, weight{weight} {}

    WeightedEdge& operator=(const WeightedEdge& edge) {
        parent = edge.parent;
        id = edge.id;
        weight = edge.weight;
        return *this;
    }

};

} // namespace internal

} // namespace zawa
#line 5 "Src/Graph/ShortestPath/ShortestPathTree.hpp"

#include <algorithm>
#include <cassert>
#include <vector>

namespace zawa {

namespace internal {

class ShortestPathTree {
public:
    using E = Edge;
    static constexpr u32 invalid() noexcept {
        return E::invalid();
    }
private:
    static constexpr u32 INVALID{E::invalid()};
    usize n_;
    u32 root_;
    std::vector<E> tree_;
    std::vector<u32> dist_;
public:
    ShortestPathTree() = default;
    ShortestPathTree(usize n, u32 root) : n_{n}, root_{root}, tree_(n), dist_(n, INVALID) {
        assert(root < n);
        tree_.shrink_to_fit();
        dist_.shrink_to_fit();
        dist_[root] = 0;
    }

    inline usize size() const noexcept {
        return n_;
    }
    inline usize root() const noexcept {
        return root_;
    }
    inline u32 parent(u32 v) const noexcept {
        assert(v < size());
        return tree_[v].parent;
    }
    inline u32 id(u32 v) const noexcept {
        assert(v < size());
        return tree_[v].id;
    }
    inline bool connect(u32 v) const noexcept {
        assert(v < size());
        return root() == v or tree_[v].exist();
    }
    inline u32 dist(u32 v) const noexcept {
        assert(v < size());
        return dist_[v];
    }

    u32 operator[](u32 v) const noexcept {
        assert(v < size());
        return dist_[v];
    }

    bool relax(u32 from, u32 to, u32 id) {
        if (dist_[to] > dist_[from] + 1) {
            dist_[to] = dist_[from] + 1;
            tree_[to].parent = from;
            tree_[to].id = id;
            return true;
        }
        return false;
    }

    std::vector<u32> pathV(u32 v) {
        assert(v < size());
        assert(connect(v));
        std::vector<u32> res(dist(v) + 1);
        res[dist(v)] = v;
        for (u32 i{dist(v)} ; i-- ; ) {
            v = parent(v);
            res[i] = v;
        }
        return res;
    }
    
    std::vector<E> pathE(u32 v) {
        assert(v < size());
        assert(connect(v));
        std::vector<E> res(dist(v));
        for (u32 i{dist(v)} ; i-- ; ) {
            res[i] = tree_[v];
            v = parent(v);
        }
        return res;
    }
};

} // namespace internal

} // namespace zawa
#line 5 "Src/Graph/ShortestPath/BFS.hpp"

#include <utility>
#line 8 "Src/Graph/ShortestPath/BFS.hpp"

namespace zawa {

class BFS {
public:
    using ShortestPathTree = internal::ShortestPathTree;
private:
    usize n_;
    std::vector<std::vector<std::pair<u32, u32>>> adj_;

    static constexpr u32 invalid() noexcept {
        return ShortestPathTree::invalid();
    }

public:
    BFS() = default;
    BFS(usize n) : n_{n}, adj_(n) {
        adj_.shrink_to_fit();
    }

    usize size() const noexcept {
        return n_;
    }
    void addDirectedEdge(u32 from, u32 to, u32 id = invalid()) {
        assert(from < size());
        assert(to < size());
        adj_[from].emplace_back(to, id);
    }
    void addUndirectedEdge(u32 u, u32 v, u32 id = invalid()) {
        assert(u < size());
        assert(v < size());
        adj_[u].emplace_back(v, id);
        adj_[v].emplace_back(u, id);
    }

    BFS(const std::vector<std::vector<u32>>& g) : n_{g.size()}, adj_(g.size()) {
        adj_.shrink_to_fit();
        for (u32 v{} ; v < size() ; v++) {
            for (u32 x : g[v]) {
                adj_[v].emplace_back(x, invalid());
            }
        }
    }

    ShortestPathTree build(u32 start) {
        std::vector<u32> queue;
        queue.reserve(n_);
        ShortestPathTree res(n_, start);
        queue.emplace_back(start);
        for (u32 head{} ; head < queue.size() ; head++) {
            u32 v{queue[head]};
            for (auto [x, id] : adj_[v]) {
                if (res.relax(v, x, id)) {
                    queue.emplace_back(x);
                }
            }
        }
        return res;
    }
};

} // namespace zawa
#line 5 "Test/Manual/abc271_d.test.cpp"

#line 7 "Test/Manual/abc271_d.test.cpp"
#include <string>
#line 10 "Test/Manual/abc271_d.test.cpp"

/*
 * ABC271-D Flip and Adjust
 * https://atcoder.jp/contests/abc271/submissions/48494158
 */

void solve() {
    using namespace zawa; 
    SetFastIO();
    int n, s; std::cin >> n >> s;
    
    auto f{[&](int card, int sum) -> int {
        return card * (s + 1) + sum;
    }};

    BFS bfs((n + 1) * (s + 1));
    for (int i{} ; i < n ; i++) {
        int a, b; std::cin >> a >> b;
        for (int j{} ; j + a <= s ; j++) {
            bfs.addDirectedEdge(f(i, j), f(i + 1, j + a), 0);
        }
        for (int j{} ; j + b <= s ; j++) {
            bfs.addDirectedEdge(f(i, j), f(i + 1, j + b), 1);
        }
    }

    auto tree{bfs.build(f(0, 0))};
    if (tree.connect(f(n, s))) {
        std::cout << "Yes\n";
        for (const auto& e : tree.pathE(f(n, s))) {
            std::cout << (e.id ? 'T' : 'H');
        }
        std::cout << '\n';
    }
    else {
        std::cout << "No" << '\n';
    }
}

int main() {
#ifdef ATCODER
    solve();
#else
    std::cout << "Hello World" << '\n';
#endif
}
Back to top page