結果
問題 | No.763 Noelちゃんと木遊び |
ユーザー |
|
提出日時 | 2018-12-20 20:35:58 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 124 ms / 2,000 ms |
コード長 | 5,484 bytes |
コンパイル時間 | 881 ms |
コンパイル使用メモリ | 89,388 KB |
最終ジャッジ日時 | 2025-01-06 19:45:24 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include <iostream>#include <type_traits>#include <algorithm>#include <string>#include <vector>#include <set>// Metafunctions {{{template <class F, class... Args>auto is_valid_fn(F fn, Args... args) -> decltype(fn(args...),std::true_type{});std::false_type is_valid_fn(...);template <class F, class... Args>struct is_valid :decltype(is_valid_fn(std::declval<F>(), std::declval<Args>()...)) {};struct is_container_impl {template <class T>auto operator() (T t) -> decltype(std::begin(t));};template <class T>struct is_container :is_valid<is_container_impl, T> {};template <class T>struct is_nonstring_container :std::integral_constant<bool,is_container<T>{} && !std::is_same<T, std::string>{}> {};// }}}// {{{ Dirty stuffsusing ll = long long;using Z = int;#define rep(i, n) for (decltype(n) i = 0; i < (n); ++i)#define rrep(i, n) for (auto i = (n); i >= 0; --i)#define btwn(i, from, below) for (auto i = (from); i < (below); ++i)#define rbtwn(i, from, above) for (auto i = (from); i >= (above); --i)#define each(e, c) for (auto&& e : c)#define all(c) std::begin(c), std::end(c)// }}}// Range {{{template <class Container>class slice_wrapper {public:using iterator = typename Container::iterator;private:Container& entity;iterator start, last;public:slice_wrapper(Container& container, std::size_t head, std::size_t tail) :entity(container),start(std::next(std::begin(container), head)),last(std::prev(std::end(container), tail)) {}iterator begin() const {return start;}iterator end() const {return last;}};template <class Container>inline slice_wrapper<Container>slice(Container& container, std::size_t head, std::size_t tail = 0) {return slice_wrapper<Container>(container, head, tail);}// }}}// I/O utlity {{{#define HEAD(x, ...) x#define READ_INPUT(T, ...) T HEAD(__VA_ARGS__); read_input(__VA_ARGS__)#define rz(...) READ_INPUT(Z, __VA_ARGS__)#define rint(...) READ_INPUT(int, __VA_ARGS__)#define rll(...) READ_INPUT(ll, __VA_ARGS__)#define rstr(s) READ_INPUT(std::string, s)#define RCONT_IMPL(c, ...) c; static_assert(is_container<decltype(c)>::value, #c " is not a container"); read_input(c, __VA_ARGS__)#define rcont(...) __VA_ARGS__ RCONT_IMPL#define rvec(...) rcont(std::vector<__VA_ARGS__>)struct is_readable_impl {template <class T>auto operator() (T t) -> decltype(std::cin >> t);};template <class T>struct is_readable :is_valid<is_readable_impl, T> {};template <class T>std::enable_if_t<is_nonstring_container<T>{}>read_input(T&, std::size_t);template <class T, class U>void read_input(std::pair<T, U>&);template <class T>std::enable_if_t<is_nonstring_container<T>{}>read_input(T&);template <class T>std::enable_if_t<is_nonstring_container<T>{}>read_input(T&, std::size_t , std::size_t, std::size_t);template <class T>std::enable_if_t<is_readable<T>{}>read_input(T& value) {std::cin >> value;}template <class T>std::enable_if_t<std::is_integral<T>{}>read_input(T& value, T offset) {read_input(value);value -= offset;}template <class T>std::enable_if_t<is_nonstring_container<T>{}>read_input(T& container, std::size_t n) {container = T(n);read_input(container);}template <class T, class U>void read_input(std::pair<T, U>& pair) {read_input(pair.first);read_input(pair.second);}template <class T>std::enable_if_t<is_nonstring_container<T>{}>read_input(T& container) {for (auto& elem : container)read_input(elem);}template <class T>std::enable_if_t<is_nonstring_container<T>{}>read_input(T& container, std::size_t n, std::size_t sentinel_l, std::size_t sentinel_r) {container = T(n);for (auto& elem : slice(container, sentinel_l, sentinel_r)) {read_input(elem);}}template <class T, class U>std::ostream& operator<<(std::ostream& os, std::pair<T, U> pair) {os << '(' << pair.first << ", " << pair.second << ')';return os;}template <class C>std::enable_if_t<is_nonstring_container<C>{}, std::ostream&>operator<< (std::ostream& os, C container) {os << '[' << *std::begin(container);for (auto& elem : slice(container, 1)) {os << ' ' << elem;}os << ']';return os;}void accelerate_IO() {std::ios_base::sync_with_stdio(false);std::cin.tie(nullptr);}// }}}// Debugging {{{#ifdef DEBUG# define show(expr) std::cerr << "\e[33m[Show : line " << __LINE__ << "] " << #expr << " = " << (expr) << "\e[m" << std::endl# define msg(message) std::cerr << "\e[33m[Message : line " << __LINE__ << "] " << message << "\e[m" << std::endl# define debug if (true)#else# define show(expr)inline void msg(...) {}# define debug if (false)#endif// }}}using namespace std;int main() {rz(n);rvec(pair<Z, Z>)(es, n - 1);vector<set<Z>> gr(n);vector<bool> exist(n, true);each(p, es) {p.first--;p.second--;gr[p.first].insert(p.second);gr[p.second].insert(p.first);}bool leaf = true;while (leaf) {leaf = false;rep(i, n) {show(i);if (!exist[i] || gr[i].size() != 1) continue;show(gr[i]);leaf = true;auto deleted = *begin(gr[i]);show(deleted);each(u, gr[deleted]) {show(u);gr[u].erase(deleted);}gr[deleted].clear();exist[deleted] = false;}}Z parts = 0;rep(i, n)if (exist[i]) parts++;cout << parts << endl;}