結果
問題 | No.1103 Directed Length Sum |
ユーザー | saxofone111 |
提出日時 | 2021-04-20 23:11:32 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,146 ms / 3,000 ms |
コード長 | 4,466 bytes |
コンパイル時間 | 2,363 ms |
コンパイル使用メモリ | 209,572 KB |
実行使用メモリ | 159,384 KB |
最終ジャッジ日時 | 2024-07-04 05:29:35 |
合計ジャッジ時間 | 15,134 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 826 ms
159,384 KB |
testcase_03 | AC | 514 ms
59,432 KB |
testcase_04 | AC | 659 ms
40,072 KB |
testcase_05 | AC | 1,146 ms
67,020 KB |
testcase_06 | AC | 398 ms
27,108 KB |
testcase_07 | AC | 77 ms
8,960 KB |
testcase_08 | AC | 131 ms
12,032 KB |
testcase_09 | AC | 46 ms
6,940 KB |
testcase_10 | AC | 185 ms
15,276 KB |
testcase_11 | AC | 709 ms
43,436 KB |
testcase_12 | AC | 415 ms
27,416 KB |
testcase_13 | AC | 197 ms
15,632 KB |
testcase_14 | AC | 36 ms
6,944 KB |
testcase_15 | AC | 314 ms
22,124 KB |
testcase_16 | AC | 798 ms
48,292 KB |
testcase_17 | AC | 813 ms
50,372 KB |
testcase_18 | AC | 179 ms
15,196 KB |
testcase_19 | AC | 730 ms
44,468 KB |
testcase_20 | AC | 60 ms
7,552 KB |
testcase_21 | AC | 122 ms
11,264 KB |
testcase_22 | AC | 596 ms
36,884 KB |
testcase_23 | AC | 332 ms
23,380 KB |
コンパイルメッセージ
main.cpp: In function 'int main()': main.cpp:224:6: warning: 'root' may be used uninitialized [-Wmaybe-uninitialized] 224 | dfs(root); | ~~~^~~~~~ main.cpp:220:6: note: 'root' was declared here 220 | ll root; | ^~~~
ソースコード
#include "bits/stdc++.h" #define MOD 1000000007 #define rep(i, n) for(ll i=0; i < (n); i++) #define rrep(i, n) for(ll i=(n)-1; i >=0; i--) #define ALL(v) v.begin(),v.end() #define rALL(v) v.rbegin(),v.rend() #define FOR(i, j, k) for(ll i=j;i<k;i++) #define debug_print(var) cerr << #var << "=" << var <<endl; #define DUMP(i, v)for(ll i=0;i<v.size();i++)cerr<<v[i]<<" " #define fi first #define se second using namespace std; typedef long long int ll; typedef vector<ll> llvec; typedef vector<double> dvec; typedef pair<ll, ll> P; typedef long double ld; struct edge{ll x, c;}; vector<llvec> e; ll mod(ll a, ll mod){ ll res = a%mod; if(res<0)res=res + mod; return res; } ll modpow(ll a, ll n, ll mod){ ll res=1; while(n>0){ if(n&1) res=res*a%mod; a=a*a%mod; n>>=1; } return res; } ll modinv(ll a, ll mod){ ll b=mod, u=1, v=0; while(b){ ll t=a/b; a-=t*b; swap(a, b); u-=t*v; swap(u, v); } u%=mod; if(u<0)u+=mod; return u; } ll gcd(ll a, ll b){ ll r = a%b; if(r==0) return b; else return gcd(b, a%b); } // @param b 1 // @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g std::pair<long long, long long> inv_gcd(long long a, long long b) { a = mod(a, b); if (a == 0) return {b, 0}; // Contracts: // [1] s - m0 * a = 0 (mod b) // [2] t - m1 * a = 0 (mod b) // [3] s * |m1| + t * |m0| <= b long long s = b, t = a; long long m0 = 0, m1 = 1; while (t) { long long u = s / t; s -= t * u; m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b // [3]: // (s - t * u) * |m1| + t * |m0 - m1 * u| // <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u) // = s * |m1| + t * |m0| <= b auto tmp = s; s = t; t = tmp; tmp = m0; m0 = m1; m1 = tmp; } // by [3]: |m0| <= b/g // by g != b: |m0| < b/g if (m0 < 0) m0 += b / s; return {s, m0}; } // (rem, mod) std::pair<long long, long long> crt(const std::vector<long long>& r, const std::vector<long long>& m) { assert(r.size() == m.size()); int n = int(r.size()); // Contracts: 0 <= r0 < m0 long long r0 = 0, m0 = 1; for (int i = 0; i < n; i++) { assert(1 <= m[i]); long long r1 = mod(r[i], m[i]), m1 = m[i]; if (m0 < m1) { std::swap(r0, r1); std::swap(m0, m1); } if (m0 % m1 == 0) { if (r0 % m1 != r1) return {0, 0}; continue; } // assume: m0 > m1, lcm(m0, m1) >= 2 * max(m0, m1) // (r0, m0), (r1, m1) -> (r2, m2 = lcm(m0, m1)); // r2 % m0 = r0 // r2 % m1 = r1 // -> (r0 + x*m0) % m1 = r1 // -> x*u0*g % (u1*g) = (r1 - r0) (u0*g = m0, u1*g = m1) // -> x = (r1 - r0) / g * inv(u0) (mod u1) // im = inv(u0) (mod u1) (0 <= im < u1) long long g, im; std::tie(g, im) = inv_gcd(m0, m1); long long u1 = (m1 / g); // |r1 - r0| < (m0 + m1) <= lcm(m0, m1) if ((r1 - r0) % g) return {0, 0}; // u1 * u1 <= m1 * m1 / g / g <= m0 * m1 / g = lcm(m0, m1) long long x = (r1 - r0) / g % u1 * im % u1; // |r0| + |m0 * x| // < m0 + m0 * (u1 - 1) // = m0 + m0 * m1 / g - m0 // = lcm(m0, m1) r0 += x * m0; m0 *= u1; // -> lcm(m0, m1) if (r0 < 0) r0 += m0; } return {r0, m0}; } bool is_prime(ll n){ ll i = 2; if(n==1)return false; if(n==2)return true; bool res = true; while(i*i <n){ if(n%i==0){ res = false; } i = i+1; } //if(i==1)res = false; if(n%i==0)res=false; return res; } #define fracMax 10000000 ll frac[fracMax]; ll ifrac[fracMax]; void gen(){ frac[0] = 1; ifrac[0] = 1; rep(i, fracMax-1){ frac[i+1] = mod((i+1)*frac[i], MOD); ifrac[i+1] = modinv(frac[i+1], MOD); } return; } ll binom(ll n, ll k){ if(k<0 or k>n){ return 0; }else{ return mod(mod(frac[n]*ifrac[n-k], MOD)*ifrac[k], MOD); } } llvec d; llvec c; ll ans; ll dfs(ll to){ for(auto ie: e[to]){ d[ie] = d[to] + 1; c[to] += dfs(ie); ans = mod(ans + (d[to]+1) * c[ie], MOD); } c[to]++; return c[to]; } /************************************** ** A main function starts from here ** ***************************************/ int main(){ ll N; cin >> N; e = vector<llvec>(N); llvec flg(N, 0); d = llvec(N, 0); c = llvec(N, 0); rep(i, N-1){ ll a, b; cin >> a >> b; a--;b--; e[a].push_back(b); flg[b]++; } ll root; rep(i, N)if(flg[i]==0)root = i; dfs(root); cout << ans << endl; return 0; }