結果
問題 | No.1103 Directed Length Sum |
ユーザー | kappybar |
提出日時 | 2020-07-03 22:21:29 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,346 ms / 3,000 ms |
コード長 | 950 bytes |
コンパイル時間 | 1,635 ms |
コンパイル使用メモリ | 172,716 KB |
実行使用メモリ | 124,524 KB |
最終ジャッジ日時 | 2023-10-17 04:29:45 |
合計ジャッジ時間 | 14,138 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 15 ms
26,364 KB |
testcase_01 | AC | 14 ms
26,364 KB |
testcase_02 | AC | 792 ms
124,524 KB |
testcase_03 | AC | 568 ms
65,812 KB |
testcase_04 | AC | 749 ms
47,240 KB |
testcase_05 | AC | 1,346 ms
61,956 KB |
testcase_06 | AC | 466 ms
40,112 KB |
testcase_07 | AC | 96 ms
30,080 KB |
testcase_08 | AC | 152 ms
31,664 KB |
testcase_09 | AC | 62 ms
28,760 KB |
testcase_10 | AC | 214 ms
33,512 KB |
testcase_11 | AC | 822 ms
49,088 KB |
testcase_12 | AC | 475 ms
40,112 KB |
testcase_13 | AC | 225 ms
33,512 KB |
testcase_14 | AC | 49 ms
28,236 KB |
testcase_15 | AC | 360 ms
37,208 KB |
testcase_16 | AC | 941 ms
51,660 KB |
testcase_17 | AC | 980 ms
52,980 KB |
testcase_18 | AC | 213 ms
33,512 KB |
testcase_19 | AC | 844 ms
49,616 KB |
testcase_20 | AC | 72 ms
29,288 KB |
testcase_21 | AC | 133 ms
31,136 KB |
testcase_22 | AC | 685 ms
45,392 KB |
testcase_23 | AC | 387 ms
38,000 KB |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) using namespace std; using ll = long long ; using P = pair<int,int> ; using pll = pair<long long,long long>; constexpr int INF = 1e9; constexpr long long LINF = 1e17; constexpr int MOD = 1000000007; constexpr double PI = 3.14159265358979323846; ll n = 1000005; vector<vector<int>> tree(n,vector<int>()); ll ans = 0; ll dfs(int i,ll depth=1,int before=-1){ ll res = 0; for(int c:tree[i]){ if(c==before) continue; ll p = dfs(c,depth+1,i); ans = (ans + (depth*p)%MOD)%MOD; res += p; } return res+1; } int main(){ cin >> n; vector<int> cnt(n); rep(i,n-1){ int a,b; cin >> a >> b; --a;--b; tree[a].push_back(b); tree[b].push_back(a); cnt[b] ++; } int id = -1; rep(i,n){ if(cnt[i]==0) id = i; } dfs(id); cout << ans << endl; return 0; }