結果
問題 | No.1103 Directed Length Sum |
ユーザー | tonnnura172 |
提出日時 | 2020-07-11 05:20:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,448 ms / 3,000 ms |
コード長 | 1,350 bytes |
コンパイル時間 | 562 ms |
コンパイル使用メモリ | 82,204 KB |
実行使用メモリ | 263,280 KB |
最終ジャッジ日時 | 2024-10-12 07:16:26 |
合計ジャッジ時間 | 14,024 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 55 ms
66,156 KB |
testcase_01 | AC | 57 ms
66,436 KB |
testcase_02 | AC | 526 ms
263,280 KB |
testcase_03 | AC | 430 ms
263,272 KB |
testcase_04 | AC | 789 ms
182,712 KB |
testcase_05 | AC | 1,448 ms
236,188 KB |
testcase_06 | AC | 517 ms
145,796 KB |
testcase_07 | AC | 142 ms
93,568 KB |
testcase_08 | AC | 203 ms
100,300 KB |
testcase_09 | AC | 117 ms
85,864 KB |
testcase_10 | AC | 261 ms
110,572 KB |
testcase_11 | AC | 872 ms
193,884 KB |
testcase_12 | AC | 493 ms
145,728 KB |
testcase_13 | AC | 270 ms
112,580 KB |
testcase_14 | AC | 107 ms
84,316 KB |
testcase_15 | AC | 406 ms
131,508 KB |
testcase_16 | AC | 1,011 ms
207,932 KB |
testcase_17 | AC | 1,054 ms
195,256 KB |
testcase_18 | AC | 252 ms
110,236 KB |
testcase_19 | AC | 919 ms
195,560 KB |
testcase_20 | AC | 126 ms
87,692 KB |
testcase_21 | AC | 175 ms
99,524 KB |
testcase_22 | AC | 732 ms
161,188 KB |
testcase_23 | AC | 419 ms
135,664 KB |
ソースコード
import sys, re from collections import deque, defaultdict, Counter from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd, log2 from itertools import accumulate, permutations, combinations, product from operator import itemgetter, mul, add from copy import deepcopy from string import ascii_lowercase, ascii_uppercase, digits from bisect import bisect, bisect_left from heapq import heappush, heappop from functools import reduce, lru_cache def input(): return sys.stdin.buffer.readline().rstrip() def INT(): return int(input()) def MAP(): return map(int, input().split()) def LIST(): return list(map(int, input().split())) def ZIP(n): return zip(*(MAP() for _ in range(n))) sys.setrecursionlimit(10 ** 9) INF = float('inf') mod = 10 ** 9 + 7 N = INT() tree = [[] for _ in range(N)] din = [0]*N for _ in range(N-1): A, B = MAP() tree[A-1].append(B-1) din[B-1] += 1 root = din.index(0) size_d = [0]*N size_u = [0]*N parent = [0]*N order = [] stack = [root] while stack: x = stack.pop() size_u[x] += 1 order.append(x) for y in tree[x]: size_u[y] += size_u[x] parent[y] = x stack.append(y) ans = 0 for v in order[::-1]: size_d[v] += 1 if v == root: break p = parent[v] s = size_d[v] ans += s * size_u[p] ans %= mod size_d[p] += s print(ans)