結果

問題 No.1928 Make a Binary Tree
ユーザー harurunharurun
提出日時 2021-12-01 12:55:28
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,961 bytes
コンパイル時間 610 ms
コンパイル使用メモリ 82,404 KB
実行使用メモリ 129,424 KB
最終ジャッジ日時 2024-11-06 04:19:56
合計ジャッジ時間 36,850 ms
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 43 RE * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

class SegTree:
def __init__(self,op,e,v):
self._op=op
self._e=e
if isinstance(v,int):
v=[e]*v
self._n=len(v)
self._log=self.ceil2()
self._size=1<<self._log
self._d=[e]*(2*self._size)
for i in range(self._n):
self._d[self._size+i]=v[i]
for i in range(self._size-1,0,-1):
self._update(i)
return
def ceil2(self):
x=0
while (1<<x)<self._n:
x+=1
return x
def set(self,p,x):
p+=self._size
self._d[p]=x
for i in range(1,self._log+1):
self._update(p>>i)
return
def get(self,p):
return self._d[p+self._size]
def prod(self,left,right):
sml=self._e
smr=self._e
left+=self._size
right+=self._size
while left<right:
if left&1:
sml=self._op(sml,self._d[left])
left+=1
if right&1:
right-=1
smr=self._op(self._d[right],smr)
left>>=1
right>>=1
return self._op(sml,smr)
def all_prod(self):
return self._d[1]
def max_right(self,left,target):
self.target=target
if left==self._n:
return self._n
left+=self._size
sm=self._e
first=True
while first or (left & -left)!=left:
first=False
while left%2==0:
left>>=1
if not self._f(self._op(sm,self._d[left])):
while left<self._size:
left*=2
if self._f(self._op(sm,self._d[left])):
sm=self._op(sm,self._d[left])
left+=1
return left-self._size
sm=self._op(sm,self._d[left])
left+=1
return self._n
def min_left(self,right,target):
self.target=target
if right==0:
return 0
right+=self._size
sm=self._e
first=True
while first or (right&-right)!=right:
first=False
right-=1
while right>1 and right%2:
right>>=1
if not self._f(self._op(self._d[right],sm)):
while right<self._size:
right=2*right+1
if self._f(self._op(self._d[right],sm)):
sm=self._op(self._d[right],sm)
right-=1
return right+1-self._size
sm=self._op(self._d[right],sm)
return 0
def _update(self,k):
self._d[k]=self._op(self._d[2*k],self._d[2*k+1])
return
def _f(self,u):
return u<self.target
def main():
N=int(input())
Graph=[[]for i in range(N)]
checked=[False]*N
for i in range(N-1):
x,y=map(int,input().split())
Graph[x-1].append(y-1)
Graph[y-1].append(x-1)
seg=SegTree(max,[-1,-1],N)
searched=[0]
def dfs(i):
pre=searched[0]
checked[i]=True
for to in Graph[i]:
if not checked[to]:
cnt=dfs(to)
seg.set(searched[0],[cnt,searched[0]])
searched[0]+=1
res=1
for j in range(2):
tmp=seg.prod(pre,searched[0])
if tmp[0]==-1:
break
res+=tmp[0]
seg.set(tmp[1],[-1,-1])
return res
ans=dfs(0)
print(ans)
return
main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0