結果
問題 | No.1365 [Cherry 1st Tune] Whose Fault? |
ユーザー |
👑 ![]() |
提出日時 | 2021-01-17 02:32:40 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 8,413 bytes |
コンパイル時間 | 297 ms |
コンパイル使用メモリ | 82,100 KB |
実行使用メモリ | 136,952 KB |
最終ジャッジ日時 | 2024-12-29 09:21:53 |
合計ジャッジ時間 | 12,209 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 12 RE * 34 |
ソースコード
#正解出力用class Fraction_Error(Exception):passclass Fraction():##入力定義def __init__(self,Numerator=0,Denominator=1):"""分数のオブジェクトを生成する.Numerator:分子Denominator:分母 (!=0)"""assert Denominator,"分母が0"if Denominator<0:Numerator*=-1Denominator*=-1self.a=Numeratorself.b=Denominatorself.__reduce()#表示定義def __str__(self):if self.b==1:return str(self.a)else:return "{}/{}".format(self.a,self.b)def __repr__(self):return self.__str__()#四則演算定義def __add__(self,other):if other.__class__==Fraction:x=self.a*other.b+self.b*other.ay=self.b*other.belif other.__class__==int:x=self.a+self.b*othery=self.belse:assert 0,"型が違う"C=Fraction(x,y)C.__reduce()return Cdef __radd__(self,other):return self+otherdef __sub__(self,other):if other.__class__==Fraction:x=self.a*other.b-self.b*other.ay=self.b*other.belif other.__class__==int:x=self.a+self.b*othery=self.belse:assert 0,"型が違う"C=Fraction(x,y)C.__reduce()return Cdef __rsub__(self,other):return -self+otherdef __mul__(self,other):if other.__class__==Fraction:x=self.a*other.ay=self.b*other.belif other.__class__==int:x=self.a*othery=self.belse:assert 0,"型が違う"C=Fraction(x,y)C.__reduce()return Cdef __rmul__(self,other):return self*otherdef __floordiv__(self,other):if other==Fraction():raise ZeroDivisionErrorH=self/otherreturn H.a//H.bdef __rfloordiv__(self,other):if self==Fraction():raise ZeroDivisionErrorH=other/selfreturn H.a//H.bdef __truediv__(self,other):assert other,"除数が0"if other.__class__==Fraction:x=self.a*other.by=self.b*other.aelif other.__class__==int:x=self.ay=self.b*otherelse:assert 0,"型が違う"C=Fraction(x,y)C.__reduce()return Cdef __rtruediv__(self,other):assert self,"除数が0"if other.__class__==Fraction:x=other.a*self.by=other.b*self.aelif other.__class__==int:x=other*self.by=self.aelse:assert 0,"型が違う"return Fraction(x,y)def __pow__(self,m):self.__reduce()alpha,beta=self.a,self.bif m<0:alpha,beta=beta,alpham=-mreturn Fraction(pow(alpha,m),pow(beta,m))#丸めdef __floor__(self):self.__reduce()return self.a//self.bdef __ceil__(self):self.__reduce()return (self.a+self.b-1)//self.b#真偽値def __bool__(self):return bool(self.a)#比較def __eq__(self,other):if other.__class__==Fraction:return self.a*other.b==self.b*other.aelif other.__class__==int:return self.a==self.b*otherelse:assert 0,"型が違う"def __nq__(self,other):return not(self==other)def __lt__(self,other):return self<=other and self!=otherdef __le__(self,other):self.__reduce()if other.__class__==Fraction:other.__reduce()return self.a*other.b<=self.b*other.aelif other.__class__==int:return self.a<=self.b*otherelse:assert 0,"型が違う"def __gt__(self,other):return other<=self and other!=selfdef __ge__(self,other):return other<=self#その他def __float__(self):return self.a/self.bdef sign(self):s=self.a*self.bif s>0:return 1elif s==0:return 0else:return -1def __reduce(self):a,b=self.a,self.bx=abs(a)y=bwhile y:x,y=y,x%yself.a//=xself.b//=x#符号def __pos__(self):return selfdef __neg__(self):return Fraction(-self.a,self.b)def __abs__(self):if self.a>0:return selfelse:return -self#その他def is_unit(self):self.__reduce()return self.a==1class Coloring_Union_Find():def __init__(self,N,f,e=0):"""0,1,...,n-1を要素として初期化する.N:要素数f:2変数関数の合成e:最初の値"""self.n=Nself.parents=[-1]*Nself.data=[e]*Nself.rank=[0]*Nself.f=fdef find(self, x):"""要素xの属している族を調べる.x:要素"""V=[]while self.parents[x]>=0:V.append(x)x=self.parents[x]for v in V:self.parents[v]=xreturn xdef union(self, x, y):"""要素x,yを同一視する.x,y:要素"""x=self.find(x)y=self.find(y)if x==y:returnself.data[x]=self.data[y]=self.f(self.data[x],self.data[y])if self.rank[x]<self.rank[y]:x,y=y,xself.parents[x]+=self.parents[y]self.parents[y]=xif self.rank[x]==self.rank[y]:self.rank[x]+=1def size(self, x):"""要素xの属している要素の数.x:要素"""return -self.parents[self.find(x)]def same(self, x, y):"""要素x,yは同一視されているか?x,y:要素"""return self.find(x) == self.find(y)def set(self,x,c):"""要素xの属する成分の色をcに変更する.x:要素c:色"""self.data[self.find(x)]=creturndef look(self,x):"""要素xの属する成分の色x:要素"""return self.data[self.find(x)]def members(self, x):"""要素xが属している族の要素.※族の要素の個数が欲しいときはsizeを使うこと!!x:要素"""root = self.find(x)return [i for i in range(self.n) if self.find(i) == root]def roots(self):"""族の名前のリスト"""return [i for i,x in enumerate(self.parents) if x < 0]def group_count(self):"""族の個数"""return len(self.roots())def all_group_members(self):"""全ての族の出力"""X={r:[] for r in self.roots()}for k in range(self.n):X[self.find(k)].append(k)return Xdef color_list(self):return [self.look(x) for x in range(self.n)]def color_map(self):return {x:self.look(x) for x in self.roots()}def __str__(self):return '\n'.join('{} [color:{}]: {}'.format(r,self.look(r),self.members(r)) for r in self.roots())def __repr__(self):return self.__str__()def adder(x,y):if x==inf or y==inf:return infelse:return x+y#================================================import sysfrom decimal import Decimalinput=sys.stdin.readlinewrite=sys.stdout.writeN=int(input())A=["*"]+list(map(int,input().split()))B=["*"]+list(map(int,input().split()))P=["*"]+list(map(int,input().split()))inf=float("inf")U=Coloring_Union_Find(N+1,lambda x,y:[x[0]+y[0],x[1]+y[1]],[0,0])Ans=Fraction()for i in range(1,N+1):d=A[i]-B[i]Ans+=d*d*P[i]if P[i]:U.set(i,[d,Fraction(1,P[i])])else:U.set(i,[d,inf])Q=int(input())S=[0]*Qfor q in range(Q):X,Y=map(int,input().split())if not U.same(X,Y):d,p=U.look(X)Ans-=d*d/pd,p=U.look(Y)Ans-=d*d/pU.union(X,Y)d,p=U.look(X)Ans+=d*d/pS[q]=float(Ans)write("\n".join(map(str,S)))