結果
問題 | No.1103 Directed Length Sum |
ユーザー | 👑 CleyL |
提出日時 | 2022-09-18 21:53:17 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,108 ms / 3,000 ms |
コード長 | 719 bytes |
コンパイル時間 | 1,108 ms |
コンパイル使用メモリ | 83,112 KB |
実行使用メモリ | 65,792 KB |
最終ジャッジ日時 | 2024-06-01 15:45:26 |
合計ジャッジ時間 | 11,952 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 729 ms
65,792 KB |
testcase_03 | AC | 521 ms
46,560 KB |
testcase_04 | AC | 607 ms
30,592 KB |
testcase_05 | AC | 1,108 ms
50,432 KB |
testcase_06 | AC | 371 ms
21,120 KB |
testcase_07 | AC | 71 ms
7,552 KB |
testcase_08 | AC | 113 ms
9,728 KB |
testcase_09 | AC | 43 ms
5,888 KB |
testcase_10 | AC | 164 ms
12,160 KB |
testcase_11 | AC | 655 ms
32,896 KB |
testcase_12 | AC | 370 ms
21,120 KB |
testcase_13 | AC | 173 ms
12,416 KB |
testcase_14 | AC | 32 ms
5,376 KB |
testcase_15 | AC | 284 ms
17,152 KB |
testcase_16 | AC | 759 ms
36,608 KB |
testcase_17 | AC | 791 ms
38,016 KB |
testcase_18 | AC | 164 ms
12,160 KB |
testcase_19 | AC | 678 ms
33,664 KB |
testcase_20 | AC | 51 ms
6,528 KB |
testcase_21 | AC | 99 ms
9,088 KB |
testcase_22 | AC | 538 ms
28,032 KB |
testcase_23 | AC | 300 ms
18,176 KB |
ソースコード
#include <iostream> #include <vector> #include <queue> using namespace std; const long long MOD = 1000000007; struct d{ int i,dep; }; int main(){ int n;cin>>n; vector<long long> A(n,-1); vector<int> C[n]; for(int i = 0; n-1 > i; i++){ int a,b;cin>>a>>b; A[--b] = --a; C[a].push_back(b); } int f = -1; for(int i = 0; n > i; i++){ if(A[i] == -1)f = i; } queue<d> B; B.push({f,0}); A[f] = 0; while(B.size()){ auto x = B.front();B.pop(); for(int i = 0; C[x.i].size() > i; i++){ A[C[x.i][i]] = x.dep+1; B.push({C[x.i][i],x.dep+1}); } } long long ans = 0; for(int i = 0; n > i; i++){ ans += A[i]*(A[i]+1)/2; } cout << ans%MOD << endl; }