結果
| 問題 | No.1365 [Cherry 1st Tune] Whose Fault? |
| ユーザー |
👑  Kazun
|
| 提出日時 | 2021-01-17 20:32:41 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,469 bytes |
| コンパイル時間 | 320 ms |
| コンパイル使用メモリ | 82,440 KB |
| 実行使用メモリ | 103,560 KB |
| 最終ジャッジ日時 | 2024-06-09 06:46:47 |
| 合計ジャッジ時間 | 8,866 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 124 ms
93,284 KB |
| testcase_01 | AC | 131 ms
86,264 KB |
| testcase_02 | AC | 129 ms
86,560 KB |
| testcase_03 | AC | 140 ms
88,448 KB |
| testcase_04 | AC | 141 ms
88,672 KB |
| testcase_05 | AC | 143 ms
89,160 KB |
| testcase_06 | AC | 138 ms
88,900 KB |
| testcase_07 | AC | 153 ms
88,832 KB |
| testcase_08 | AC | 145 ms
88,948 KB |
| testcase_09 | AC | 134 ms
86,204 KB |
| testcase_10 | AC | 128 ms
86,152 KB |
| testcase_11 | AC | 134 ms
86,656 KB |
| testcase_12 | AC | 138 ms
88,652 KB |
| testcase_13 | TLE | - |
| testcase_14 | TLE | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
ソースコード
#正解出力用
class Fraction_Error(Exception):
pass
class Fraction():
##入力定義
def __init__(self,Numerator=0,Denominator=1):
"""分数のオブジェクトを生成する.
Numerator:分子
Denominator:分母 (!=0)
"""
assert Denominator,"分母が0"
if Denominator<0:
Numerator*=-1
Denominator*=-1
self.a=Numerator
self.b=Denominator
self.__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.a
y=self.b*other.b
elif other.__class__==int:
x=self.a+self.b*other
y=self.b
else:
assert 0,"型が違う"
C=Fraction(x,y)
C.__reduce()
return C
def __radd__(self,other):
return self+other
def __sub__(self,other):
if other.__class__==Fraction:
x=self.a*other.b-self.b*other.a
y=self.b*other.b
elif other.__class__==int:
x=self.a+self.b*other
y=self.b
else:
assert 0,"型が違う"
C=Fraction(x,y)
C.__reduce()
return C
def __rsub__(self,other):
return -self+other
def __mul__(self,other):
if other.__class__==Fraction:
x=self.a*other.a
y=self.b*other.b
elif other.__class__==int:
x=self.a*other
y=self.b
else:
assert 0,"型が違う"
C=Fraction(x,y)
C.__reduce()
return C
def __rmul__(self,other):
return self*other
def __floordiv__(self,other):
if other==Fraction():
raise ZeroDivisionError
H=self/other
return H.a//H.b
def __rfloordiv__(self,other):
if self==Fraction():
raise ZeroDivisionError
H=other/self
return H.a//H.b
def __truediv__(self,other):
assert other,"除数が0"
if other.__class__==Fraction:
x=self.a*other.b
y=self.b*other.a
elif other.__class__==int:
x=self.a
y=self.b*other
else:
assert 0,"型が違う"
C=Fraction(x,y)
C.__reduce()
return C
def __rtruediv__(self,other):
assert self,"除数が0"
if other.__class__==Fraction:
x=other.a*self.b
y=other.b*self.a
elif other.__class__==int:
x=other*self.b
y=self.a
else:
assert 0,"型が違う"
return Fraction(x,y)
def __pow__(self,m):
self.__reduce()
alpha,beta=self.a,self.b
if m<0:
alpha,beta=beta,alpha
m=-m
return Fraction(pow(alpha,m),pow(beta,m))
#丸め
def __floor__(self):
self.__reduce()
return self.a//self.b
def __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.a
elif other.__class__==int:
return self.a==self.b*other
else:
return False
def __nq__(self,other):
return not(self==other)
def __lt__(self,other):
return self<=other and self!=other
def __le__(self,other):
self.__reduce()
if other.__class__==Fraction:
other.__reduce()
return self.a*other.b<=self.b*other.a
elif other.__class__==int:
return self.a<=self.b*other
else:
return False
def __gt__(self,other):
return other<=self and other!=self
def __ge__(self,other):
return other<=self
#その他
def __float__(self):
return self.a/self.b
def sign(self):
s=self.a*self.b
if s>0:return 1
elif s==0:return 0
else:return -1
def __reduce(self):
a,b=self.a,self.b
x=abs(a)
y=b
while y:
x,y=y,x%y
self.a//=x
self.b//=x
#符号
def __pos__(self):
return self
def __neg__(self):
return Fraction(-self.a,self.b)
def __abs__(self):
if self.a>0:
return self
else:
return -self
#その他
def is_unit(self):
self.__reduce()
return self.a==1
class Coloring_Union_Find():
def __init__(self,N,f,e=0):
"""0,1,...,n-1を要素として初期化する.
N:要素数
f:2変数関数の合成
e:最初の値
"""
self.n=N
self.parents=[-1]*N
self.data=[e]*N
self.rank=[0]*N
self.f=f
def 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]=x
return x
def union(self, x, y):
"""要素x,yを同一視する.
x,y:要素
"""
x=self.find(x)
y=self.find(y)
if x==y:
return
self.data[x]=self.data[y]=self.f(self.data[x],self.data[y])
if self.rank[x]<self.rank[y]:
x,y=y,x
self.parents[x]+=self.parents[y]
self.parents[y]=x
if self.rank[x]==self.rank[y]:
self.rank[x]+=1
def 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)]=c
return
def 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 X
def 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 inf
else:
return x+y
#================================================
import sys
from decimal import Decimal
input=sys.stdin.readline
write=sys.stdout.write
N=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],adder(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]*Q
for q in range(Q):
X,Y=map(int,input().split())
if not U.same(X,Y):
d,p=U.look(X)
if p!=inf:
Ans-=d*d/p
d,p=U.look(Y)
if p!=inf:
Ans-=d*d/p
U.union(X,Y)
d,p=U.look(X)
if p!=inf:
Ans+=d*d/p
S[q]=float(Ans)
write("\n".join(map(str,S)))