結果
問題 | No.1124 Earthquake Safety |
ユーザー | NyaanNyaan |
提出日時 | 2020-07-22 22:15:01 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 491 ms / 3,000 ms |
コード長 | 15,235 bytes |
コンパイル時間 | 3,287 ms |
コンパイル使用メモリ | 218,008 KB |
実行使用メモリ | 113,128 KB |
最終ジャッジ日時 | 2023-09-04 21:12:07 |
合計ジャッジ時間 | 20,327 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 1 ms
4,380 KB |
testcase_04 | AC | 1 ms
4,380 KB |
testcase_05 | AC | 2 ms
4,380 KB |
testcase_06 | AC | 2 ms
4,380 KB |
testcase_07 | AC | 8 ms
4,376 KB |
testcase_08 | AC | 90 ms
17,304 KB |
testcase_09 | AC | 385 ms
45,480 KB |
testcase_10 | AC | 271 ms
113,128 KB |
testcase_11 | AC | 1 ms
4,376 KB |
testcase_12 | AC | 2 ms
4,380 KB |
testcase_13 | AC | 2 ms
4,384 KB |
testcase_14 | AC | 397 ms
45,488 KB |
testcase_15 | AC | 387 ms
45,472 KB |
testcase_16 | AC | 397 ms
45,836 KB |
testcase_17 | AC | 405 ms
45,488 KB |
testcase_18 | AC | 430 ms
45,612 KB |
testcase_19 | AC | 383 ms
45,480 KB |
testcase_20 | AC | 393 ms
45,548 KB |
testcase_21 | AC | 391 ms
45,432 KB |
testcase_22 | AC | 374 ms
45,420 KB |
testcase_23 | AC | 372 ms
45,936 KB |
testcase_24 | AC | 388 ms
46,024 KB |
testcase_25 | AC | 370 ms
46,264 KB |
testcase_26 | AC | 366 ms
46,312 KB |
testcase_27 | AC | 357 ms
49,768 KB |
testcase_28 | AC | 376 ms
49,712 KB |
testcase_29 | AC | 389 ms
61,716 KB |
testcase_30 | AC | 385 ms
61,824 KB |
testcase_31 | AC | 454 ms
87,736 KB |
testcase_32 | AC | 445 ms
83,092 KB |
testcase_33 | AC | 491 ms
81,368 KB |
testcase_34 | AC | 469 ms
87,168 KB |
testcase_35 | AC | 347 ms
45,136 KB |
testcase_36 | AC | 302 ms
44,488 KB |
testcase_37 | AC | 332 ms
45,264 KB |
testcase_38 | AC | 298 ms
44,620 KB |
testcase_39 | AC | 301 ms
44,168 KB |
testcase_40 | AC | 304 ms
44,796 KB |
testcase_41 | AC | 289 ms
44,160 KB |
testcase_42 | AC | 299 ms
44,404 KB |
testcase_43 | AC | 297 ms
44,696 KB |
testcase_44 | AC | 290 ms
44,496 KB |
testcase_45 | AC | 283 ms
44,076 KB |
testcase_46 | AC | 287 ms
44,432 KB |
testcase_47 | AC | 287 ms
44,204 KB |
testcase_48 | AC | 287 ms
44,232 KB |
testcase_49 | AC | 294 ms
44,192 KB |
testcase_50 | AC | 2 ms
4,376 KB |
testcase_51 | AC | 1 ms
4,380 KB |
testcase_52 | AC | 2 ms
4,376 KB |
testcase_53 | AC | 1 ms
4,376 KB |
testcase_54 | AC | 1 ms
4,380 KB |
testcase_55 | AC | 1 ms
4,376 KB |
testcase_56 | AC | 1 ms
4,380 KB |
testcase_57 | AC | 1 ms
4,376 KB |
ソースコード
#pragma region kyopro_template #include <bits/stdc++.h> #define pb push_back #define eb emplace_back #define fi first #define se second #define each(x, v) for (auto &x : v) #define all(v) (v).begin(), (v).end() #define sz(v) ((int)(v).size()) #define mem(a, val) memset(a, val, sizeof(a)) #define ini(...) \ int __VA_ARGS__; \ in(__VA_ARGS__) #define inl(...) \ long long __VA_ARGS__; \ in(__VA_ARGS__) #define ins(...) \ string __VA_ARGS__; \ in(__VA_ARGS__) #define inc(...) \ char __VA_ARGS__; \ in(__VA_ARGS__) #define in2(s, t) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i]); \ } #define in3(s, t, u) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i]); \ } #define in4(s, t, u, v) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i], v[i]); \ } #define rep(i, N) for (long long i = 0; i < (long long)(N); i++) #define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--) #define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++) #define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--) #define reg(i, a, b) for (long long i = (a); i < (b); i++) #define die(...) \ do { \ out(__VA_ARGS__); \ return; \ } while (0) using namespace std; using ll = long long; template <class T> using V = vector<T>; using vi = vector<int>; using vl = vector<long long>; using vvi = vector<vector<int>>; using vd = V<double>; using vs = V<string>; using vvl = vector<vector<long long>>; using P = pair<long long, long long>; using vp = vector<P>; using pii = pair<int, int>; using vpi = vector<pair<int, int>>; constexpr int inf = 1001001001; constexpr long long infLL = (1LL << 61) - 1; template <typename T, typename U> inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; } template <typename T, typename U> inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; } template <typename T, typename U> T ceil(T a, U b) { return (a + b - 1) / b; } constexpr long long TEN(int n) { long long ret = 1, x = 10; while (n) { if (n & 1) ret *= x; x *= x; n >>= 1; } return ret; } template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) { os << p.first << " " << p.second; return os; } template <typename T, typename U> istream &operator>>(istream &is, pair<T, U> &p) { is >> p.first >> p.second; return is; } template <typename T> ostream &operator<<(ostream &os, const vector<T> &v) { int s = (int)v.size(); for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i]; return os; } template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; } void in() {} template <typename T, class... U> void in(T &t, U &... u) { cin >> t; in(u...); } void out() { cout << "\n"; } template <typename T, class... U> void out(const T &t, const U &... u) { cout << t; if (sizeof...(u)) cout << " "; out(u...); } void solve(); #ifdef NyaanDebug #include "NyaanDebug.h" #define trc(...) \ do { \ cerr << #__VA_ARGS__ << " = "; \ dbg_out(__VA_ARGS__); \ } while (0) #define trca(v, N) \ do { \ cerr << #v << " = "; \ array_out(v, N); \ } while (0) #define trcc(v) \ do { \ cerr << #v << " = {"; \ each(x, v) { cerr << " " << x << ","; } \ cerr << "}" << endl; \ } while (0) #else #define trc(...) #define trca(...) #define trcc(...) int main() { solve(); } #endif inline int popcnt(unsigned long long a) { return __builtin_popcountll(a); } inline int lsb(unsigned long long a) { return __builtin_ctzll(a); } inline int msb(unsigned long long a) { return 63 - __builtin_clzll(a); } template <typename T> inline int getbit(T a, int i) { return (a >> i) & 1; } template <typename T> inline void setbit(T &a, int i) { a |= (1LL << i); } template <typename T> inline void delbit(T &a, int i) { a &= ~(1LL << i); } template <typename T> int lb(const vector<T> &v, const T &a) { return lower_bound(begin(v), end(v), a) - begin(v); } template <typename T> int ub(const vector<T> &v, const T &a) { return upper_bound(begin(v), end(v), a) - begin(v); } template <typename T> vector<T> mkrui(const vector<T> &v) { vector<T> ret(v.size() + 1); for (int i = 0; i < int(v.size()); i++) ret[i + 1] = ret[i] + v[i]; return ret; }; template <typename T> vector<T> mkuni(const vector<T> &v) { vector<T> ret(v); sort(ret.begin(), ret.end()); ret.erase(unique(ret.begin(), ret.end()), ret.end()); return ret; } template <typename F> vector<int> mkord(int N, F f) { vector<int> ord(N); iota(begin(ord), end(ord), 0); sort(begin(ord), end(ord), f); return ord; } template <typename T = int> vector<T> mkiota(int N) { vector<T> ret(N); iota(begin(ret), end(ret), 0); return ret; } template <typename T = int> vector<T> mkinv(vector<T> &v) { vector<T> inv(v.size()); for (int i = 0; i < (int)v.size(); i++) inv[v[i]] = i; return inv; } struct IoSetupNya { IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(7); } } iosetupnya; #pragma endregion constexpr int MOD = /** 998244353; //*/ 1000000007; template <typename G = vector<vector<int>>> struct HeavyLightDecomposition { G &g; int idx; vector<int> size, depth, in, out, nxt, par; HeavyLightDecomposition(G &g, int root = 0) : g(g), idx(0), size(g.size(), 0), depth(g.size(), 0), in(g.size(), -1), out(g.size(), -1), nxt(g.size(), 0), par(g.size(), root) { dfs_sz(root); dfs_hld(root); } void build(int root) { dfs_sz(root); dfs_hld(root); } void dfs_sz(int cur) { size[cur] = 1; for (auto &dst : g[cur]) { if (dst == par[cur]) { if (g[cur].size() >= 2 && int(dst) == int(g[cur][0])) swap(g[cur][0], g[cur][1]); else continue; } depth[dst] = depth[cur] + 1; par[dst] = cur; dfs_sz(dst); size[cur] += size[dst]; if (size[dst] > size[g[cur][0]]) { swap(dst, g[cur][0]); } } } void dfs_hld(int cur) { in[cur] = idx++; for (auto dst : g[cur]) { if (dst == par[cur]) continue; nxt[dst] = (int(dst) == int(g[cur][0]) ? nxt[cur] : int(dst)); dfs_hld(dst); } out[cur] = idx; } template <typename F> void edge_query(int u, int v, const F &f) { while (1) { if (in[u] > in[v]) swap(u, v); if (nxt[u] != nxt[v]) { f(in[nxt[v]], in[v] + 1); v = par[nxt[v]]; } else { if (u != v) f(in[u] + 1, in[v] + 1); break; } } } template <typename F> void node_query(int u, int v, const F &f) { while (1) { if (in[u] > in[v]) swap(u, v); if (nxt[u] != nxt[v]) { f(in[nxt[v]], in[v] + 1); v = par[nxt[v]]; } else { f(in[u], in[v] + 1); break; } } } template <typename F> void sub_edge_query(int u, const F &f) { f(in[u] + 1, out[u]); } template <typename F> void sub_node_query(int u, const F &f) { f(in[u], out[u]); } int lca(int a, int b) { while (nxt[a] != nxt[b]) { if (in[a] < in[b]) swap(a, b); a = par[nxt[a]]; } return depth[a] < depth[b] ? a : b; } }; // LazySegmentTree template <typename T, typename E, typename F, typename G, typename H> struct LST { int n, height; F f; G g; H h; T ti; E ei; vector<T> dat; vector<E> laz; LST(int n, F f, G g, H h, T ti, E ei) : f(f), g(g), h(h), ti(ti), ei(ei) { init(n); } LST(const vector<T> &v, F f, G g, H h, T ti, E ei) : f(f), g(g), h(h), ti(ti), ei(ei) { init((int)v.size()); build(v); } void init(int n_) { n = 1; height = 0; while (n < n_) n <<= 1, height++; dat.assign(2 * n, ti); laz.assign(2 * n, ei); } void build(const vector<T> &v) { int n_ = v.size(); init(n_); for (int i = 0; i < n_; i++) dat[n + i] = v[i]; for (int i = n - 1; i; i--) dat[i] = f(dat[(i << 1) | 0], dat[(i << 1) | 1]); } inline T reflect(int k) { return laz[k] == ei ? dat[k] : g(dat[k], laz[k]); } inline void eval(int k) { if (laz[k] == ei) return; laz[(k << 1) | 0] = h(laz[(k << 1) | 0], laz[k]); laz[(k << 1) | 1] = h(laz[(k << 1) | 1], laz[k]); dat[k] = reflect(k); laz[k] = ei; } inline void thrust(int k) { for (int i = height; i; i--) eval(k >> i); } inline void recalc(int k) { while (k >>= 1) dat[k] = f(reflect((k << 1) | 0), reflect((k << 1) | 1)); } void update(int a, int b, E x) { thrust(a += n); thrust(b += n - 1); for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) { if (l & 1) laz[l] = h(laz[l], x), l++; if (r & 1) --r, laz[r] = h(laz[r], x); } recalc(a); recalc(b); } void set_val(int a, T x) { thrust(a += n); dat[a] = x; laz[a] = ei; recalc(a); } T query(int a, int b) { thrust(a += n); thrust(b += n - 1); T vl = ti, vr = ti; for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) { if (l & 1) vl = f(vl, reflect(l++)); if (r & 1) vr = f(reflect(--r), vr); } return f(vl, vr); } }; template <typename T> struct edge { int src, to; T cost; edge(int to, T cost) : src(-1), to(to), cost(cost) {} edge(int src, int to, T cost) : src(src), to(to), cost(cost) {} edge &operator=(const int &x) { to = x; return *this; } operator int() const { return to; } }; template <typename T> using Edges = vector<edge<T>>; template <typename T> using WeightedGraph = vector<Edges<T>>; using UnweightedGraph = vector<vector<int>>; // Input of (Unweighted) Graph UnweightedGraph graph(int N, int M = -1, bool is_directed = false, bool is_1origin = true) { UnweightedGraph g(N); if (M == -1) M = N - 1; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; if (is_1origin) x--, y--; g[x].pb(y); if (!is_directed) g[y].pb(x); } return g; } // Input of Weighted Graph template <typename T> WeightedGraph<T> wgraph(int N, int M = -1, bool is_directed = false, bool is_1origin = true) { WeightedGraph<T> g(N); if (M == -1) M = N - 1; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; T c; cin >> c; if (is_1origin) x--, y--; g[x].eb(x, y, c); if (!is_directed) g[y].eb(y, x, c); } return g; } // Depth of Rooted Tree // unvisited nodes : d = -1 vector<int> Depth(UnweightedGraph &g, int start = 0) { vector<int> d(g.size(), -1); auto dfs = [&](auto rec, int cur, int par = -1) -> void { d[cur] = par == -1 ? 0 : d[par] + 1; each(dst, g[cur]) { if (dst == par) continue; rec(rec, dst, cur); } }; dfs(dfs, start); return d; } // Diameter of Tree pair<int, int> Diameter(UnweightedGraph &g, int start = 0) { auto d = Depth(g, start); int u = max_element(begin(d), end(d)) - begin(d); d = Depth(g, u); int v = max_element(begin(d), end(d)) - begin(d); return make_pair(u, v); } template <typename G> vector<int> path(G &g, int u, int v) { vi ret; int end = 0; auto dfs = [&](auto rec, int cur, int par = -1) -> void { ret.pb(cur); if (cur == v) { end = 1; return; } each(dst, g[cur]) { if (dst == par) continue; rec(rec, dst, cur); if (end) return; } if (end) return; ret.pop_back(); }; dfs(dfs, u); return ret; } template <uint32_t mod> struct LazyMontgomeryModInt { using mint = LazyMontgomeryModInt; using i32 = int32_t; using u32 = uint32_t; using u64 = uint64_t; static constexpr u32 get_r() { u32 ret = mod; for (i32 i = 0; i < 4; ++i) ret *= 2 - mod * ret; return -ret; } static constexpr u32 r = get_r(); static constexpr u32 n2 = -u64(mod) % mod; static_assert(-r * mod == 1, "invalid, r * mod != 1"); static_assert(mod < (1 << 30), "invalid, mod >= 2 ^ 30"); static_assert((mod & 1) == 1, "invalid, mod % 2 == 0"); u32 a; constexpr LazyMontgomeryModInt() : a(0) {} constexpr LazyMontgomeryModInt(const int64_t &b) : a(reduce(u64(b % mod + mod) * n2)){}; static constexpr u32 reduce(const u64 &b) { return (b + u64(u32(b) * r) * mod) >> 32; } constexpr mint &operator+=(const mint &b) { if (i32(a += b.a - 2 * mod) < 0) a += 2 * mod; return *this; } constexpr mint &operator-=(const mint &b) { if (i32(a -= b.a) < 0) a += 2 * mod; return *this; } constexpr mint &operator*=(const mint &b) { a = reduce(u64(a) * b.a); return *this; } constexpr mint &operator/=(const mint &b) { *this *= b.inverse(); return *this; } constexpr mint operator+(const mint &b) const { return mint(*this) += b; } constexpr mint operator-(const mint &b) const { return mint(*this) -= b; } constexpr mint operator*(const mint &b) const { return mint(*this) *= b; } constexpr mint operator/(const mint &b) const { return mint(*this) /= b; } constexpr bool operator==(const mint &b) const { return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a); } constexpr bool operator!=(const mint &b) const { return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a); } constexpr mint operator-() const { return mint() - mint(*this); } constexpr u32 get() const { u32 ret = reduce(a); return ret >= mod ? ret - mod : ret; } constexpr mint pow(u64 n) const { mint ret(1), mul(*this); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } friend ostream &operator<<(ostream &os, const mint &b) { return os << b.get(); } friend istream &operator>>(istream &is, mint &b) { int64_t t; is >> t; b = LazyMontgomeryModInt<mod>(t); return (is); } constexpr mint inverse() const { return pow(mod - 2); } static constexpr u32 get_mod() { return mod; } }; using mint = LazyMontgomeryModInt<MOD>; using vm = vector<mint>; void solve() { ini(N); auto g = graph(N); HeavyLightDecomposition<vvi> hld(g); vm e = {mint(1), mint(1), mint(2).inverse(), mint(6).inverse()}; auto mul = [](const vm &a, const vm &b) { vm c(sz(a) + sz(b) - 1); rep(i, sz(a)) rep(j, sz(b)) c[i + j] += a[i] * b[j]; return c; }; V<vm> ans(N); mint bns = 0; auto dfs = [&](auto rec, int cur, int par = -1) -> vm { ans[cur] = e; each(dst, g[cur]) { if (dst == par) continue; ans[cur] = mul(ans[cur], rec(rec, dst, cur)); ans[cur].resize(4); } trc(cur,hld.size[cur]); vm ret = ans[cur]; bns += ans[cur][3] * mint(6) * mint(2).pow(max(0, N - hld.size[cur] - 1)); ret[0] += mint(2).pow(hld.size[cur] - 1); return ret; }; dfs(dfs, 0); rep(i, N) ans[i][2] *= 2, ans[i][3] *= 6; trc(ans); out(bns); }