結果
問題 | No.1103 Directed Length Sum |
ユーザー |
![]() |
提出日時 | 2020-07-03 22:12:25 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 746 ms / 3,000 ms |
コード長 | 5,920 bytes |
コンパイル時間 | 2,192 ms |
コンパイル使用メモリ | 190,328 KB |
実行使用メモリ | 163,268 KB |
最終ジャッジ日時 | 2023-10-17 03:53:31 |
合計ジャッジ時間 | 9,435 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,348 KB |
testcase_01 | AC | 2 ms
4,348 KB |
testcase_02 | AC | 390 ms
163,268 KB |
testcase_03 | AC | 199 ms
74,508 KB |
testcase_04 | AC | 374 ms
55,248 KB |
testcase_05 | AC | 746 ms
93,376 KB |
testcase_06 | AC | 205 ms
37,108 KB |
testcase_07 | AC | 39 ms
11,380 KB |
testcase_08 | AC | 63 ms
15,800 KB |
testcase_09 | AC | 25 ms
8,476 KB |
testcase_10 | AC | 89 ms
20,220 KB |
testcase_11 | AC | 414 ms
60,196 KB |
testcase_12 | AC | 217 ms
37,372 KB |
testcase_13 | AC | 97 ms
20,748 KB |
testcase_14 | AC | 20 ms
7,156 KB |
testcase_15 | AC | 163 ms
29,852 KB |
testcase_16 | AC | 495 ms
67,188 KB |
testcase_17 | AC | 539 ms
69,760 KB |
testcase_18 | AC | 92 ms
20,220 KB |
testcase_19 | AC | 459 ms
61,516 KB |
testcase_20 | AC | 31 ms
9,532 KB |
testcase_21 | AC | 59 ms
14,480 KB |
testcase_22 | AC | 391 ms
50,828 KB |
testcase_23 | AC | 185 ms
31,896 KB |
コンパイルメッセージ
main.cpp: In function 'Pl dfs(mat<int>&, int)': main.cpp:202:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 202 | auto [c, s] = dfs(g, nv); | ^ main.cpp: In function 'int main()': main.cpp:224:9: warning: 'root' may be used uninitialized [-Wmaybe-uninitialized] 224 | int root; | ^~~~
ソースコード
/* #region header */ #ifdef LOCAL #include "/Users/takakurashokichi/Desktop/atcoder/cxx-prettyprint-master/prettyprint.hpp" #define debug(x) cout << x << endl #else #define debug(...) 42 #endif #pragma GCC optimize("Ofast") #include <bits/stdc++.h> //types using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; typedef pair < ll , ll > Pl; typedef pair < int, int > Pi; typedef vector<ll> vl; typedef vector<int> vi; typedef vector<char> vc; template< typename T > using mat = vector< vector< T > >; typedef vector<vector<int>> vvi; typedef vector<vector<long long>> vvl; typedef vector<vector<char>> vvc; template< int mod > struct modint { int x; modint() : x(0) {} modint(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {} modint &operator+=(const modint &p) { if((x += p.x) >= mod) x -= mod; return *this; } modint &operator-=(const modint &p) { if((x += mod - p.x) >= mod) x -= mod; return *this; } modint &operator*=(const modint &p) { x = (int) (1LL * x * p.x % mod); return *this; } modint &operator/=(const modint &p) { *this *= p.inverse(); return *this; } modint operator-() const { return modint(-x); } modint operator+(const modint &p) const { return modint(*this) += p; } modint operator-(const modint &p) const { return modint(*this) -= p; } modint operator*(const modint &p) const { return modint(*this) *= p; } modint operator/(const modint &p) const { return modint(*this) /= p; } bool operator==(const modint &p) const { return x == p.x; } bool operator!=(const modint &p) const { return x != p.x; } modint inverse() const { int a = x, b = mod, u = 1, v = 0, t; while(b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); } return modint(u); } modint pow(int64_t n) const { modint ret(1), mul(x); while(n > 0) { if(n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } friend ostream &operator<<(ostream &os, const modint &p) { return os << p.x; } friend istream &operator>>(istream &is, modint &a) { int64_t t; is >> t; a = modint< mod >(t); return (is); } static int get_mod() { return mod; } }; //abreviations #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define rep_(i, a_, b_, a, b, ...) for (int i = (a), max_i = (b); i < max_i; i++) #define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__) #define rrep_(i, a_, b_, a, b, ...) for (int i = (b-1), min_i = (a); i >= min_i; i--) #define rrep(i, ...) rrep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__) #define SZ(x) ((int)(x).size()) #define pb(x) push_back(x) #define eb(x) emplace_back(x) #define mp make_pair #define print(x) cout << x << endl #define vprint(x) rep(i, x.xize())cout << x[i] << ' '; cout << endl #define vsum(x) accumulate(all(x), 0LL) #define vmax(a) *max_element(all(a)) #define vmin(a) *min_element(all(a)) #define lb(c, x) distance((c).begin(), lower_bound(all(c), (x))) #define ub(c, x) distance((c).begin(), upper_bound(all(c), (x))) //functions //gcd(0, x) fails. ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; } ll lcm(ll a, ll b) { return a/gcd(a, b)*b;} template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; } template< typename T > T mypow(T x, ll n) { T ret = 1; while(n > 0) { if(n & 1) (ret *= x); (x *= x); n >>= 1; } return ret; } ll modpow(ll x, ll n, const ll mod) { ll ret = 1; while(n > 0) { if(n & 1) (ret *= x); (x *= x); n >>= 1; x%=mod; ret%=mod; } return ret; } uint64_t my_rand(void) { static uint64_t x = 88172645463325252ULL; x = x ^ (x << 13); x = x ^ (x >> 7); return x = x ^ (x << 17); } int popcnt(ull x) { return __builtin_popcountll(x); } //graph template 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; } bool operator<(const edge<T> &r) const { return cost < r.cost; } 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 > >; struct Timer { clock_t start_time; void start() { start_time = clock(); } int lap() { //return x ms. return (clock()-start_time)*1000 / CLOCKS_PER_SEC; } }; /* #endregion*/ //constant #define inf 1000000005 #define INF 4000000004000000000LL #define mod 1000000007LL #define endl '\n' typedef modint<mod> mint; const long double eps = 0.000001; const long double PI = 3.141592653589793; //library mat<Pl> sub; Pl dfs(mat<int>& g, int v){ ll res = 0; ll count = 1; for(int nv:g[v]){ auto [c, s] = dfs(g, nv); sub[v].pb(mp(c, s)); res+=s; count+=c; } res+=count; return mp(count, res); } int main(){ cin.tie(0); ios::sync_with_stdio(0); cout << setprecision(20); int n; cin>>n; sub.resize(n); mat<int> g(n); vi deg(n); rep(i, n-1){ int a, b; cin>>a>>b; a--;b--; g[a].pb(b); deg[b]++; } int root; rep(i, n){ if(deg[i]==0)root = i; } dfs(g, root); mint ans = 0; rep(i, n){ for(auto s:sub[i]){ ans+=s.second; } } print(ans); }