結果
問題 | No.1928 Make a Binary Tree |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
class SegTree:def __init__(self,op,e,v):self._op=opself._e=eif isinstance(v,int):v=[e]*vself._n=len(v)self._log=self.ceil2()self._size=1<<self._logself._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)returndef ceil2(self):x=0while (1<<x)<self._n:x+=1return xdef set(self,p,x):p+=self._sizeself._d[p]=xfor i in range(1,self._log+1):self._update(p>>i)returndef get(self,p):return self._d[p+self._size]def prod(self,left,right):sml=self._esmr=self._eleft+=self._sizeright+=self._sizewhile left<right:if left&1:sml=self._op(sml,self._d[left])left+=1if right&1:right-=1smr=self._op(self._d[right],smr)left>>=1right>>=1return self._op(sml,smr)def all_prod(self):return self._d[1]def max_right(self,left,target):self.target=targetif left==self._n:return self._nleft+=self._sizesm=self._efirst=Truewhile first or (left & -left)!=left:first=Falsewhile left%2==0:left>>=1if not self._f(self._op(sm,self._d[left])):while left<self._size:left*=2if self._f(self._op(sm,self._d[left])):sm=self._op(sm,self._d[left])left+=1return left-self._sizesm=self._op(sm,self._d[left])left+=1return self._ndef min_left(self,right,target):self.target=targetif right==0:return 0right+=self._sizesm=self._efirst=Truewhile first or (right&-right)!=right:first=Falseright-=1while right>1 and right%2:right>>=1if not self._f(self._op(self._d[right],sm)):while right<self._size:right=2*right+1if self._f(self._op(self._d[right],sm)):sm=self._op(self._d[right],sm)right-=1return right+1-self._sizesm=self._op(self._d[right],sm)return 0def _update(self,k):self._d[k]=self._op(self._d[2*k],self._d[2*k+1])returndef _f(self,u):return u<self.targetdef main():N=int(input())Graph=[[]for i in range(N)]checked=[False]*Nfor 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]=Truefor to in Graph[i]:if not checked[to]:cnt=dfs(to)seg.set(searched[0],[cnt,searched[0]])searched[0]+=1res=1for j in range(2):tmp=seg.prod(pre,searched[0])if tmp[0]==-1:breakres+=tmp[0]seg.set(tmp[1],[-1,-1])return resans=dfs(0)print(ans)returnmain()