結果
問題 | No.2360 Path to Integer |
ユーザー | 👑 SPD_9X2 |
提出日時 | 2023-06-23 22:47:29 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 354 ms / 2,500 ms |
コード長 | 1,464 bytes |
コンパイル時間 | 278 ms |
コンパイル使用メモリ | 86,800 KB |
実行使用メモリ | 107,364 KB |
最終ジャッジ日時 | 2023-09-13 17:53:21 |
合計ジャッジ時間 | 4,909 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 94 ms
71,544 KB |
testcase_01 | AC | 98 ms
71,528 KB |
testcase_02 | AC | 94 ms
71,356 KB |
testcase_03 | AC | 93 ms
71,628 KB |
testcase_04 | AC | 93 ms
71,588 KB |
testcase_05 | AC | 92 ms
71,588 KB |
testcase_06 | AC | 93 ms
71,516 KB |
testcase_07 | AC | 111 ms
77,152 KB |
testcase_08 | AC | 146 ms
80,220 KB |
testcase_09 | AC | 334 ms
102,872 KB |
testcase_10 | AC | 313 ms
107,364 KB |
testcase_11 | AC | 315 ms
106,568 KB |
testcase_12 | AC | 241 ms
101,376 KB |
testcase_13 | AC | 354 ms
103,064 KB |
testcase_14 | AC | 317 ms
101,568 KB |
testcase_15 | AC | 339 ms
102,068 KB |
testcase_16 | AC | 294 ms
100,908 KB |
ソースコード
""" 全方位木dpだよな dp[v] = 頂点v以下全てのパスについての現時点の総和 """ import sys from sys import stdin from collections import deque inf = float("inf") N = int(stdin.readline()) A = list(map(int,stdin.readline().split())) lis = [ [] for i in range(N) ] for i in range(N-1): u,v = map(int,stdin.readline().split()) u -= 1 v -= 1 lis[u].append(v) lis[v].append(u) dlis = [inf] * N dlis[0] = 0 q = deque([0]) visit = [] plis = [0] * N while q: v = q.popleft() visit.append(v) for nex in lis[v]: if dlis[nex] > dlis[v] + 1: dlis[nex] = dlis[v] + 1 plis[nex] = v q.append(nex) mod = 998244353 chsum = [0] * N chnum = [1] * N ans = 0 # dfs1 for v in reversed(visit): na = A[v] chsum[v] *= pow(10,len(str(na)),mod) chsum[v] += chnum[v] * na chsum[v] %= mod ans += chsum[v] ans %= mod if plis[v] != v: chsum[plis[v]] += chsum[v] chnum[plis[v]] += chnum[v] # dfs2 for v in visit[1:]: vp = plis[v] ap = A[vp] psum = chsum[plis[v]] # まず、自分のキヨを取り除く psum -= chsum[v] * pow(10,len(str(ap)),mod) psum -= chnum[v] * ap psum %= mod # 自分側に持ってきて、加算 na = A[v] psum *= pow(10,len(str(na)),mod) psum += (N-chnum[v]) * na ans += psum ans %= mod chsum[v] += psum chsum[v] %= mod print (ans % mod)