#932683 (Python3) No.1365 [Cherry 1st Tune] Whose Fault?

提出ソース

結果

問題	No.1365 [Cherry 1st Tune] Whose Fault?
ユーザー	vwxyz
提出日時	2023-11-30 17:07:10
言語	Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果	RE
実行時間	-
コード長	5,185 bytes
コンパイル時間	338 ms
コンパイル使用メモリ	13,184 KB
実行使用メモリ	26,632 KB
最終ジャッジ日時	2024-09-26 14:10:33
合計ジャッジ時間	7,296 ms
ジャッジサーバーID （参考情報）	judge3 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	40 ms 12,160 KB
testcase_01	AC	39 ms 12,288 KB
testcase_02	AC	40 ms 12,288 KB
testcase_03	AC	40 ms 12,288 KB
testcase_04	AC	38 ms 12,160 KB
testcase_05	AC	39 ms 12,160 KB
testcase_06	AC	38 ms 12,288 KB
testcase_07	AC	40 ms 12,288 KB
testcase_08	AC	40 ms 12,288 KB
testcase_09	AC	38 ms 12,416 KB
testcase_10	RE	-
testcase_11	AC	39 ms 12,288 KB
testcase_12	RE	-
testcase_13	RE	-
testcase_14	RE	-
testcase_15	RE	-
testcase_16	RE	-
testcase_17	RE	-
testcase_18	RE	-
testcase_19	RE	-
testcase_20	RE	-
testcase_21	RE	-
testcase_22	RE	-
testcase_23	RE	-
testcase_24	RE	-
testcase_25	RE	-
testcase_26	RE	-
testcase_27	RE	-
testcase_28	RE	-
testcase_29	RE	-
testcase_30	RE	-
testcase_31	RE	-
testcase_32	RE	-
testcase_33	RE	-
testcase_34	RE	-
testcase_35	RE	-
testcase_36	RE	-
testcase_37	RE	-
testcase_38	RE	-
testcase_39	RE	-
testcase_40	RE	-
testcase_41	RE	-
testcase_42	RE	-
testcase_43	RE	-
testcase_44	RE	-
testcase_45	AC	588 ms 12,416 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

import bisect
import copy
import decimal
import fractions
import heapq
import itertools
import math
import random
import sys
import time
from collections import Counter,deque,defaultdict
from functools import lru_cache,reduce
from heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_max
def _heappush_max(heap,item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappushpop_max(heap, item):
    if heap and item < heap[0]:
        item, heap[0] = heap[0], item
        heapq._siftup_max(heap, 0)
    return item
from math import gcd as GCD
read=sys.stdin.read
readline=sys.stdin.readline
readlines=sys.stdin.readlines
write=sys.stdout.write
#import pypyjit
#pypyjit.set_param('max_unroll_recursion=-1')
#sys.set_int_max_str_digits(10**9)

class UnionFind:
    def __init__(self,N,label=None,f=None,weighted=False,rollback=False):
        self.N=N
        self.parents=[None]*self.N
        self.size=[1]*self.N
        self.roots={i for i in range(self.N)}
        self.label=label
        if self.label!=None:
            self.label=[x for x in label]
        self.f=f
        self.weighted=weighted
        if self.weighted:
            self.weight=[0]*self.N
        self.rollback=rollback
        if self.rollback:
            self.operate_list=[]
            self.operate_set=[]

    def Find(self,x):
        stack=[]
        while self.parents[x]!=None:
            stack.append(x)
            x=self.parents[x]
        if not self.rollback:
            if self.weighted:
                w=0
                for y in stack[::-1]:
                    self.parents[y]=x
                    w+=self.weight[y]
                    self.weight[y]=w
            else:
                for y in stack[::-1]:
                    self.parents[y]=x
        return x

    def Union(self,x,y,w=None):
        root_x=self.Find(x)
        root_y=self.Find(y)
        if self.rollback:
            self.operate_list.append([])
            self.operate_set.append([])
        if root_x==root_y:
            if self.weighted:
                if self.weight[y]-self.weight[x]==w:
                    return True
                else:
                    return False
        else:
            if self.size[root_x]<self.size[root_y]:
                x,y=y,x
                root_x,root_y=root_y,root_x
                if self.weighted:
                    w=-w
            if self.rollback:
                self.operate_list[-1].append((self.parents,root_y,self.parents[root_y]))
                self.operate_list[-1].append((self.size,root_x,self.size[root_x]))
                self.operate_set[-1].append(root_y)
                if self.label!=None:
                    self.operate_list[-1]((self.label,root_x,self.label[root_x]))
                if self.weighted:
                    self.operate_list[-1].append((self.weight,root_y,self.weight[root_y]))
            self.parents[root_y]=root_x
            self.size[root_x]+=self.size[root_y]
            self.roots.remove(root_y)
            if self.label!=None:
                self.label[root_x]=self.f(self.label[root_x],self.label[root_y])
            if self.weighted:
                self.weight[root_y]=w+self.weight[x]-self.weight[y]

    def Size(self,x):
        return self.size[self.Find(x)]

    def Same(self,x,y):
        return self.Find(x)==self.Find(y)

    def Label(self,x):
        return self.label[self.Find(x)]

    def Weight(self,x,y):
        root_x=self.Find(x)
        root_y=self.Find(y)
        if root_x!=root_y:
            return None
        return self.weight[y]-self.weight[x]

    def Roots(self):
        return list(self.roots)

    def Linked_Components_Count(self):
        return len(self.roots)

    def Linked_Components(self):
        linked_components=defaultdict(list)
        for x in range(self.N):
            linked_components[self.Find(x)].append(x)
        return linked_components
    
    def Rollback(self):
        assert self.rollback
        if self.operate_list:
            for lst,x,v in self.operate_list.pop():
                lst[x]=v
            for x in self.operate_set.pop():
                self.roots.add(x)            
            return True
        else:
            return False

    def __str__(self):
        linked_components=defaultdict(list)
        for x in range(self.N):
            linked_components[self.Find(x)].append(x)
        return "\n".join(f"{r}: {linked_components[r]}" for r in sorted(list(linked_components.keys())))

N=int(readline())
A=list(map(int,readline().split()))
B=list(map(int,readline().split()))
P=list(map(int,readline().split()))
def f(tpl0,tpl1):
    a0,b0,c0,p0,ip0=tpl0
    a1,b1,c1,p1,ip1=tpl1
    return (a0+a1,b0+b1,c0+c1,p0+p1,ip0+ip1)
UF=UnionFind(N,label=[(A[x],B[x],1,P[x],1/P[x]) for x in range(N)],f=f)
Q=int(readline())
ans=sum(p*(a-b)**2 for p,a,b in zip(P,A,B))
for q in range(Q):
    X,Y=map(int,readline().split())
    X-=1;Y-=1
    if not UF.Same(X,Y):
        a,b,c,p,ip=UF.Label(X)
        ans-=abs(a-b)**2/ip
        a,b,c,p,ip=UF.Label(Y)
        ans-=abs(a-b)**2/ip
        UF.Union(X,Y)
        a,b,c,p,ip=UF.Label(X)
        ans+=abs(a-b)**2/ip
    print(ans)

yukicoder

結果

テストケース

ソースコード