結果
問題 | No.1718 Random Squirrel |
ユーザー |
![]() |
提出日時 | 2021-11-16 00:24:33 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 500 ms / 2,000 ms |
コード長 | 2,947 bytes |
コンパイル時間 | 430 ms |
コンパイル使用メモリ | 82,448 KB |
実行使用メモリ | 136,736 KB |
最終ジャッジ日時 | 2024-12-15 09:39:55 |
合計ジャッジ時間 | 10,207 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 31 |
ソースコード
from sys import stdinn, m, *indata = map(int, stdin.read().split())offset = 0g = [[] for i in range(n+1)]for i in range(n-1):s, t = indata[offset + 2*i],indata[offset + 2*i+1]g[s].append((t,i))g[t].append((s,i))offset += (n-1)*2d = [False for i in range(n+1)]for i in range(m):d[indata[offset + i]] = Trueque = [(1,0)]dp = [-1 for i in range(n+1)]dpdist = [-1 for i in range(n+1)]check = [0 for i in range(n+1)]while que:now, inout = que.pop()if inout == 0:check[now] = 1que.append((now,1))for i, ind in g[now]:if check[i] == 0:que.append((i,0))else:kari = -1distmax = -1check[now] = 2for i, ind in g[now]:if check[i] == 2:if dp[i] != -1:kari += dp[i] + 2distmax = max(distmax,dpdist[i])if kari != -1:kari += 1distmax += 1else:if d[now]:kari = 0distmax = max(distmax,0)dp[now] = karidpdist[now] = distmaxdp2 = [-1 for i in range(n+1)]dpdist2 = [-1 for i in range(n+1)]que = [(1,-1)]check = [False for i in range(n+1)]while que:now, come = que.pop()check[now] = Trueruiseki = [0]ruisekidist = [-1]for i, ind in g[now]:kari = ruiseki[-1]distmax = ruisekidist[-1]if ind != come:if dpdist[i] != -1:kari = kari + dp[i] + 2distmax = max(distmax,dpdist[i])else:if dpdist2[ind] != -1:kari = kari + dp2[ind] + 2distmax = max(distmax,dpdist2[ind])ruiseki.append(kari)ruisekidist.append(distmax)ruiseki2 = [0]ruisekidist2 = [-1]for i, ind in reversed(g[now]):kari = ruiseki2[-1]distmax = ruisekidist2[-1]if ind != come:if dpdist[i] != -1:kari = kari + dp[i] + 2distmax = max(distmax,dpdist[i])else:if dpdist2[ind] != -1:kari = kari + dp2[ind] + 2distmax = max(distmax,dpdist2[ind])ruiseki2.append(kari)ruisekidist2.append(distmax)dp[now] = ruiseki[-1]dpdist[now] = ruisekidist[-1] + 1val = 0for i, ind in g[now]:if ind != come:kari = ruiseki[val] + ruiseki2[-2-val]distmax = max(ruisekidist[val], ruisekidist2[-2-val])dp2[ind] = kariif distmax != -1:dpdist2[ind] = distmax + 1else:if d[now]:dpdist2[ind] = 0else:dpdist2[ind] = -1val += 1for i, ind in g[now]:if not check[i]:que.append((i, ind))for i in range(1,n+1):ans = dp[i] - dpdist[i]print("{}".format(ans))