#932540 (Python3) No.1170 Never Want to Walk

提出ソース

結果

問題	No.1170 Never Want to Walk
ユーザー	vwxyz
提出日時	2023-11-29 22:45:11
言語	Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果	AC
実行時間	1,579 ms / 2,000 ms
コード長	5,095 bytes
コンパイル時間	454 ms
コンパイル使用メモリ	13,056 KB
実行使用メモリ	60,444 KB
最終ジャッジ日時	2024-09-26 13:44:45
合計ジャッジ時間	23,168 ms
ジャッジサーバーID （参考情報）	judge1 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	47 ms 12,288 KB
testcase_01	AC	48 ms 12,160 KB
testcase_02	AC	44 ms 12,032 KB
testcase_03	AC	43 ms 12,288 KB
testcase_04	AC	43 ms 12,032 KB
testcase_05	AC	44 ms 12,160 KB
testcase_06	AC	43 ms 12,416 KB
testcase_07	AC	43 ms 12,160 KB
testcase_08	AC	44 ms 12,288 KB
testcase_09	AC	43 ms 12,288 KB
testcase_10	AC	44 ms 12,288 KB
testcase_11	AC	44 ms 12,288 KB
testcase_12	AC	48 ms 12,544 KB
testcase_13	AC	49 ms 12,160 KB
testcase_14	AC	50 ms 12,544 KB
testcase_15	AC	49 ms 12,544 KB
testcase_16	AC	49 ms 12,672 KB
testcase_17	AC	50 ms 12,160 KB
testcase_18	AC	49 ms 12,416 KB
testcase_19	AC	51 ms 12,672 KB
testcase_20	AC	50 ms 12,544 KB
testcase_21	AC	49 ms 12,672 KB
testcase_22	AC	51 ms 12,416 KB
testcase_23	AC	51 ms 12,672 KB
testcase_24	AC	51 ms 12,288 KB
testcase_25	AC	51 ms 12,544 KB
testcase_26	AC	51 ms 12,416 KB
testcase_27	AC	1,493 ms 51,780 KB
testcase_28	AC	1,477 ms 50,832 KB
testcase_29	AC	1,478 ms 52,264 KB
testcase_30	AC	1,487 ms 52,864 KB
testcase_31	AC	1,494 ms 51,696 KB
testcase_32	AC	1,496 ms 58,616 KB
testcase_33	AC	1,519 ms 57,528 KB
testcase_34	AC	1,520 ms 59,484 KB
testcase_35	AC	1,517 ms 59,096 KB
testcase_36	AC	1,479 ms 58,452 KB
testcase_37	AC	1,563 ms 59,924 KB
testcase_38	AC	1,579 ms 60,444 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,A,B=map(int,readline().split())
X=list(map(int,readline().split()))
UF=UnionFind(N)
imos=[0]*N
a,b=0,0
for i in range(N):
    while a<i or a+1<N and X[a]-X[i]<A:
        a+=1
    while b<i or b+1<N and X[b+1]-X[i]<=B:
        b+=1
    if a<=b and A<=X[a]-X[i]:
        UF.Union(i,a)
        UF.Union(i,b)
        imos[a]+=1
        imos[b]-=1
for i in range(1,N):
    imos[i]+=imos[i-1]
for i in range(N-1):
    if imos[i]:
        UF.Union(i,i+1)
ans_lst=[None]*N
for lst in UF.Linked_Components().values():
    for x in lst:
        ans_lst[x]=len(lst)
print(*ans_lst,sep="\n")

yukicoder

結果

テストケース

ソースコード