結果

問題 No.1976 Cut then Connect
コンテスト
ユーザー lilictaka
提出日時 2022-09-29 22:03:09
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,279 bytes
コンパイル時間 317 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 132,312 KB
最終ジャッジ日時 2024-12-22 18:29:50
合計ジャッジ時間 16,844 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 5 WA * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

from itertools import combinations
from heapq import heappop,heappush
from collections import deque
class Const_Tree():
    def __init__(self,N) -> None:
        self.const_edge = [[] for _ in range(N)]
        self.parent = [-1 for _ in range(N)]
        self.rev_edge = [[] for _ in range(N)]
        self.q = deque()
        self.edge = [[] for _ in range(N)]
        self.N = N
    def add_edge(self,u,v):
        self.edge[u].append(v)
    def const(self,st):
        self.q.append(st)
        seen = [False for _ in range(self.N)]
        while self.q:
            now = self.q.popleft()
            seen[now] = True
            for next in self.edge[now]:
                if not seen[next]:
                    self.q.append(next)
                    self.const_edge[now].append(next)
                    self.parent[next] = now
                    self.rev_edge[next].append(now)
        self.q = deque()
        self.parts = [1 for _ in range(self.N)]#部分木の数
        for i in range(self.N):
            if len(self.const_edge[i]) == 0:
                self.q.append(i)
        self.cnt = [0 for _ in range(self.N)]
        while self.q:
            now = self.q.popleft()
            for next in self.rev_edge[now]:
                self.parts[next] += self.parts[now]
                self.cnt[next] += 1
                if self.cnt[next] == len(self.const_edge[next]):
                    self.q.append(next)
def topological_sort(G):
    ret = []
    start = []
    par_count = [0] * len(G)
    for u in range(len(G)):
        for v in G[u]:
            par_count[v] += 1
    for v in range(len(G)):
        if par_count[v] == 0:
            start.append(v)

    while start:
        u = start.pop()
        ret.append(u)
        for v in G[u]:
            par_count[v] -= 1
            if par_count[v] == 0:
                start.append(v)

    if any(c > 0 for c in par_count):
        # G is not a DAG
        return None
    return ret

N = int(input())
ct = Const_Tree(N)
for _ in range(N-1):
    u,v = map(int,input().split())
    u-=1
    v-=1
    ct.add_edge(u,v)
    ct.add_edge(v,u)
ct.const(0)
edge = ct.const_edge
P = ct.parent
downmemo = [[] for _ in range(N)]
down = [0] * N
up = [0] * (N)
upsub = [0] * N
tp = topological_sort(edge)
dlen = [1]  * N
def f(List,c):
    tmp = []
    while List:
        x,u = heappop(List)
        tmp.append((x,u))
    for x,u in tmp:
        heappush(List,(x,u))
    if len(List) <=1:
        return 0
    elif len(List) == 2:
        for x,u in tmp:
            if u != c:
                return -x
    elif len(List) ==3:
        for i,k in combinations([l for l in range(3)],2):
            if tmp[i][1] != c and tmp[k][1] != c:
                return -tmp[i][0] - tmp[k][0] - 1
def g(List):
    tmp = []
    while List:
        x,u = heappop(List)
        tmp.append((x,u))
    for x,u in tmp:
        heappush(List,(x,u))
    if len(List) == 0:
        return 1
    elif len(List) == 1:
        return -tmp[0][0]
    elif len(List) >=2:
        return -tmp[0][0] - tmp[1][0] -1
def m(List,c):
    tmp = []
    while List:
        x,u = heappop(List)
        tmp.append((x,u))
    for x,u in tmp:
        heappush(List,(x,u))
    if len(List) == 0:
        return 0
    if len(List) == 1:
        return 1
    else:
        for x,u in tmp:
            if u != c:
                return -tmp[0][0]


for u in tp[::-1]:
    for cu in edge[u]:
        dlen[u] = max(dlen[cu]+1,dlen[u])
        heappush(downmemo[u],(-dlen[u],u))
        if len(downmemo[u]) > 3:
            tmp = []
            for _ in range(3):
                x,u = heappop(downmemo[u])
                tmp.append((x,u))
            while downmemo[u]:
                x,u = heappop(downmemo[u])
            for x,u in tmp:
                heappush(downmemo[u],(x,u))
    for cu in edge[u]:
        up[cu] = max(f(downmemo[u],cu),up[cu])
for u in tp:
    up[u] = max(upsub[u],up[u])
    for cu in edge[u]:
        upsub[cu] = max(m(downmemo[u],cu),upsub[cu])
        up[cu] = max(up[u],up[cu])
        upsub[cu] = max(upsub[cu],upsub[u] + 1)
ans = [0] * N
for u in range(N):
    down[u] = max(g(downmemo[u]) , down[u])
    if up[u] != 0 :
        ans[u] = (up[u]+1)//2 + (down[u] + 1)//2
    else:
        ans[u] = down[u]-1
print(min(ans))
0