結果
問題 | No.1124 Earthquake Safety |
ユーザー | KoD |
提出日時 | 2020-07-22 23:41:34 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 495 ms / 3,000 ms |
コード長 | 6,541 bytes |
コンパイル時間 | 2,833 ms |
コンパイル使用メモリ | 83,764 KB |
実行使用メモリ | 76,924 KB |
最終ジャッジ日時 | 2023-09-05 05:16:07 |
合計ジャッジ時間 | 19,495 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,380 KB |
testcase_05 | AC | 1 ms
4,380 KB |
testcase_06 | AC | 2 ms
4,380 KB |
testcase_07 | AC | 9 ms
4,380 KB |
testcase_08 | AC | 113 ms
10,792 KB |
testcase_09 | AC | 384 ms
25,552 KB |
testcase_10 | AC | 386 ms
76,924 KB |
testcase_11 | AC | 1 ms
4,380 KB |
testcase_12 | AC | 2 ms
4,380 KB |
testcase_13 | AC | 2 ms
4,380 KB |
testcase_14 | AC | 419 ms
25,636 KB |
testcase_15 | AC | 416 ms
25,828 KB |
testcase_16 | AC | 421 ms
25,680 KB |
testcase_17 | AC | 414 ms
25,736 KB |
testcase_18 | AC | 412 ms
25,568 KB |
testcase_19 | AC | 412 ms
25,584 KB |
testcase_20 | AC | 416 ms
25,832 KB |
testcase_21 | AC | 418 ms
25,540 KB |
testcase_22 | AC | 416 ms
25,840 KB |
testcase_23 | AC | 379 ms
25,480 KB |
testcase_24 | AC | 375 ms
25,444 KB |
testcase_25 | AC | 370 ms
25,860 KB |
testcase_26 | AC | 367 ms
25,736 KB |
testcase_27 | AC | 373 ms
28,488 KB |
testcase_28 | AC | 373 ms
28,460 KB |
testcase_29 | AC | 404 ms
37,588 KB |
testcase_30 | AC | 404 ms
37,708 KB |
testcase_31 | AC | 456 ms
57,280 KB |
testcase_32 | AC | 459 ms
53,504 KB |
testcase_33 | AC | 492 ms
51,820 KB |
testcase_34 | AC | 495 ms
56,456 KB |
testcase_35 | AC | 363 ms
25,532 KB |
testcase_36 | AC | 352 ms
25,300 KB |
testcase_37 | AC | 355 ms
26,828 KB |
testcase_38 | AC | 350 ms
26,352 KB |
testcase_39 | AC | 342 ms
26,024 KB |
testcase_40 | AC | 343 ms
26,788 KB |
testcase_41 | AC | 339 ms
26,188 KB |
testcase_42 | AC | 339 ms
26,876 KB |
testcase_43 | AC | 339 ms
26,800 KB |
testcase_44 | AC | 338 ms
26,800 KB |
testcase_45 | AC | 333 ms
26,524 KB |
testcase_46 | AC | 331 ms
26,736 KB |
testcase_47 | AC | 330 ms
26,464 KB |
testcase_48 | AC | 326 ms
26,536 KB |
testcase_49 | AC | 337 ms
26,516 KB |
testcase_50 | AC | 2 ms
4,388 KB |
testcase_51 | AC | 1 ms
4,384 KB |
testcase_52 | AC | 1 ms
4,384 KB |
testcase_53 | AC | 1 ms
4,384 KB |
testcase_54 | AC | 1 ms
4,384 KB |
testcase_55 | AC | 2 ms
4,384 KB |
testcase_56 | AC | 1 ms
4,380 KB |
testcase_57 | AC | 1 ms
4,380 KB |
ソースコード
#line 1 "main.cpp" /** * @title Template */ #include <iostream> #include <algorithm> #include <utility> #include <numeric> #include <vector> #include <array> template <class T, class U> inline bool chmin(T &lhs, const U &rhs) { if (lhs > rhs) { lhs = rhs; return true; } return false; } template <class T, class U> inline bool chmax(T &lhs, const U &rhs) { if (lhs < rhs) { lhs = rhs; return true; } return false; } struct range { using itr = int64_t; struct iterator { itr i; constexpr iterator(itr i_) noexcept : i(i_) { } constexpr void operator ++ () noexcept { ++i; } constexpr itr operator * () const noexcept { return i; } constexpr bool operator != (iterator x) const noexcept { return i != x.i; } }; const iterator l, r; constexpr range(itr l_, itr r_) noexcept : l(l_), r(std::max(l_, r_)) { } constexpr iterator begin() const noexcept { return l; } constexpr iterator end() const noexcept { return r; } }; struct revrange { using itr = int64_t; struct iterator { itr i; constexpr iterator(itr i_) noexcept : i(i_) { } constexpr void operator ++ () noexcept { --i; } constexpr itr operator * () const noexcept { return i; } constexpr bool operator != (iterator x) const noexcept { return i != x.i; } }; const iterator l, r; constexpr revrange(itr l_, itr r_) noexcept : l(l_ - 1), r(std::max(l_, r_) - 1) { } constexpr iterator begin() const noexcept { return r; } constexpr iterator end() const noexcept { return l; } }; #line 2 "/Users/kodamankod/Desktop/Programming/Library/algebraic/modular.cpp" #include <cstdint> #line 5 "/Users/kodamankod/Desktop/Programming/Library/algebraic/modular.cpp" template <uint32_t Modulus> class modular { public: using value_type = uint32_t; using max_type = uint64_t; static constexpr value_type mod = Modulus; static constexpr value_type get_mod() noexcept { return mod; } static_assert(mod >= 2, "invalid mod :: smaller than 2"); static_assert(mod < (value_type(1) << 31), "invalid mod :: over 2^31"); template <class T> static constexpr value_type normalize(T value_) noexcept { if (value_ < 0) { value_ = -value_; value_ %= mod; if (value_ == 0) return 0; return mod - value_; } return value_ % mod; } private: value_type value; public: constexpr modular() noexcept : value(0) { } template <class T> explicit constexpr modular(T value_) noexcept : value(normalize(value_)) { } template <class T> explicit constexpr operator T() const noexcept { return static_cast<T>(value); } constexpr value_type get() const noexcept { return value; } constexpr modular operator - () const noexcept { return modular(mod - value); } constexpr modular operator ~ () const noexcept { return inverse(); } constexpr value_type &extract() noexcept { return value; } constexpr modular inverse() const noexcept { return power(mod - 2); } constexpr modular power(max_type exp) const noexcept { modular res(1), mult(*this); while (exp > 0) { if (exp & 1) res *= mult; mult *= mult; exp >>= 1; } return res; } constexpr modular operator + (const modular &rhs) const noexcept { return modular(*this) += rhs; } constexpr modular& operator += (const modular &rhs) noexcept { if ((value += rhs.value) >= mod) value -= mod; return *this; } constexpr modular operator - (const modular &rhs) const noexcept { return modular(*this) -= rhs; } constexpr modular& operator -= (const modular &rhs) noexcept { if ((value += mod - rhs.value) >= mod) value -= mod; return *this; } constexpr modular operator * (const modular &rhs) const noexcept { return modular(*this) *= rhs; } constexpr modular& operator *= (const modular &rhs) noexcept { value = (max_type) value * rhs.value % mod; return *this; } constexpr modular operator / (const modular &rhs) const noexcept { return modular(*this) /= rhs; } constexpr modular& operator /= (const modular &rhs) noexcept { return (*this) *= rhs.inverse(); } constexpr bool zero() const noexcept { return value == 0; } constexpr bool operator == (const modular &rhs) const noexcept { return value == rhs.value; } constexpr bool operator != (const modular &rhs) const noexcept { return value != rhs.value; } friend std::ostream& operator << (std::ostream &stream, const modular &rhs) { return stream << rhs.value; } }; /** * @title Modint */ #line 2 "/Users/kodamankod/Desktop/Programming/Library/other/fix_point.cpp" #line 4 "/Users/kodamankod/Desktop/Programming/Library/other/fix_point.cpp" template <class Func> struct fix_point: private Func { explicit constexpr fix_point(Func &&func): Func(std::forward<Func>(func)) { } template <class... Args> constexpr decltype(auto) operator () (Args &&... args) const { return Func::operator()(*this, std::forward<Args>(args)...); } }; template <class Func> constexpr decltype(auto) make_fix_point(Func &&func) { return fix_point<Func>(std::forward<Func>(func)); } /** * @title Lambda Recursion */ #line 57 "main.cpp" using i32 = int32_t; using i64 = int64_t; using u32 = uint32_t; using u64 = uint64_t; constexpr i32 inf32 = (i32(1) << 30) - 1; constexpr i64 inf64 = (i64(1) << 62) - 1; using m32 = modular<1000000007>; int main() { i32 N; std::cin >> N; std::vector<std::vector<i32>> graph(N); for (auto i: range(1, N)) { i32 a, b; std::cin >> a >> b; --a; --b; graph[a].push_back(b); graph[b].push_back(a); } std::vector<i32> size(N); std::vector<std::array<m32, 4>> dp(N); for (auto &arr: dp) { arr.fill(m32()); } m32 ans; fix_point([&](auto dfs, i32 u, i32 p) -> void { dp[u][0] = m32(1); dp[u][1] = m32(1); size[u] = 1; for (auto v: graph[u]) { if (v == p) continue; dfs(v, u); std::array<m32, 4> next{}; for (auto i: range(0, 4)) { next[i] = dp[u][i] * m32(2).power(size[v] - 1); } for (auto i: range(0, 4)) { for (auto j: range(0, 4)) { if (i + j < 4) { next[i + j] += dp[u][i] * dp[v][j]; } } } dp[u] = std::move(next); size[u] += size[v]; } // for (auto i: range(0, 4)) { // std::cout << dp[u][i] << ' '; // } // std::cout << '\n'; m32 tmp = dp[u][1] + dp[u][2] * m32(6) + dp[u][3] * m32(6); if (p == -1) ans += tmp; else ans += tmp * m32(2).power((N - 1) - size[u]); })(0, -1); std::cout << ans << '\n'; return 0; }