#852077 (PyPy3) No.529 帰省ラッシュ

提出ソース
結果

問題	No.529 帰省ラッシュ
ユーザー	prin_kemkem
提出日時	2023-03-24 11:02:32
言語	PyPy3 (7.3.15)
結果	AC
実行時間	2,247 ms / 4,500 ms
コード長	15,588 bytes
コンパイル時間	241 ms
コンパイル使用メモリ	81,760 KB
実行使用メモリ	168,396 KB
最終ジャッジ日時	2023-10-18 20:02:05
合計ジャッジ時間	21,520 ms
ジャッジサーバーID （参考情報）	judge15 / judge13
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	52 ms 63,052 KB
testcase_01	AC	53 ms 63,052 KB
testcase_02	AC	53 ms 63,052 KB
testcase_03	AC	54 ms 63,052 KB
testcase_04	AC	192 ms 78,736 KB
testcase_05	AC	186 ms 78,840 KB
testcase_06	AC	203 ms 79,044 KB
testcase_07	AC	200 ms 78,908 KB
testcase_08	AC	1,334 ms 131,044 KB
testcase_09	AC	1,511 ms 131,872 KB
testcase_10	AC	1,884 ms 155,988 KB
testcase_11	AC	1,896 ms 157,272 KB
testcase_12	AC	978 ms 120,680 KB
testcase_13	AC	901 ms 161,740 KB
testcase_14	AC	752 ms 127,440 KB
testcase_15	AC	2,247 ms 168,064 KB
testcase_16	AC	2,231 ms 168,396 KB
testcase_17	AC	1,531 ms 164,344 KB
testcase_18	AC	1,516 ms 164,640 KB
testcase_19	AC	1,515 ms 164,912 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
from collections import defaultdict, deque, Counter
import copy
from itertools import combinations, permutations, product, accumulate
from heapq import heapify, heappop, heappush
import math
import bisect
import sys
# sys.setrecursionlimit(700000)
input = lambda: sys.stdin.readline().rstrip('\n')
inf = float('inf')
mod1 = 10**9+7
mod2 = 998244353
def ceil_div(x, y): return -(-x//y)

#################################################

class LowLink():
    def __init__(self, adj):
        self.n = len(adj)
        self.ord = [None]*self.n
        self.low = [None]*self.n
        self.son = [[] for _ in range(self.n)] # son[i] := 頂点iの子を格納したlist
        self.back_edge = [[] for _ in range(N)] # back_edge[i] := 頂点iから出る後退辺の終点を格納したlist
        self.tps = [] # 頂点のトポロジカルソート

        # DFSでord, son, parent, tpsを求め、lowを初期化
        t = 0 # 今までに訪れた頂点数
        stack = [(None, 0)] # 直前にいた頂点, 今いる頂点
        while stack: 
            pre, now = stack.pop()
            if self.ord[now] is not None: # 直前に通った辺が後退辺ならば
                if self.ord[pre] < self.ord[now]: continue # 後退辺を根側から進んでいた場合は無視
                self.low[pre] = min(self.low[pre], self.ord[now]) # low[pre]をord[now]でchmin
                self.back_edge[pre].append(now)
                continue
            if pre is not None:
                self.son[pre].append(now)
            self.tps.append(now)
            self.ord[now] = t # 行きがけ順を書き込む
            self.low[now] = self.ord[now] # low[now]をord[now]で初期化
            t += 1
            for next in adj[now]:
                if next == pre: continue
                stack.append((now, next))

        # ボトムアップ順にchminしてlowを求める
        for u in reversed(self.tps[1:]):
            for v in self.son[u]:
                self.low[u] = min(self.low[u], self.low[v])

    # 二重辺連結成分分解
    def two_edge_connected_component(self):
        tecc = [] # tecc[i] := 連結成分iに属する頂点の番号を格納したlist
        tecc_idx = [None]*self.n # tecc_idx[i] := 頂点iが属する連結成分の番号(上記teccにおけるindexに対応)
        tecc_tree = [] # 連結成分を頂点、橋を辺としたグラフ(木)の隣接リスト
        sub_roots = [(None, 0)] # 橋を見つけるごとに、その先は部分木として別にDFSしなおす。
        idx = 0 # 今いる頂点の連結成分の番号
        while sub_roots:
            stack = [sub_roots.pop()] # 部分木の根からDFS
            tecc.append([]) # 今いる頂点の連結成分を格納するlistを追加
            tecc_tree.append([]) # 今いる頂点の連結成分の隣接先を格納するlistを追加
            while stack:
                pre, now = stack.pop()
                tecc[idx].append(now) # 今いる頂点を連結成分idxに追加
                tecc_idx[now] = idx # 今いる頂点の連結成分の番号idxを記録
                if pre is not None and idx != tecc_idx[pre]: # 直前に橋を通ってきていたら
                    tecc_tree[idx].append(tecc_idx[pre]) # その橋で繋がれた2つの連結成分を辺で結ぶ
                    tecc_tree[tecc_idx[pre]].append(idx)
                for next in self.son[now]:
                    if self.low[next] > self.ord[now]: # 橋なら
                        sub_roots.append((now, next)) # その先は別の連結成分
                    else: # そうでないなら
                        stack.append((now, next)) # その先は同じ連結成分なのでDFSを続ける
            idx += 1
        return tecc, tecc_idx, tecc_tree

    # 二重頂点連結成分分解
    def biconnected_component(self):
        bce = [] # bce[i] := 連結成分iに属する辺を格納したlist
        bcv = [] # bcv[i] := 連結成分iに属する頂点を格納したlist
        is_ap = [False]*self.n # is_ap[i] := 頂点iは関節点であるか(True/False)
        sub_roots = [(None, 0)] #「ある子に対する関節点」を見つけるごとに、その子以降は部分木として別にDFSしなおす。
        idx = 0 # 今いる頂点の連結成分の番号
        while sub_roots:
            stack = [sub_roots.pop()] # 部分木の根からDFS
            bce.append([]) # 今いる頂点の連結成分に含まれる辺を格納するlistを追加
            bcv.append([]) # 今いる頂点の連結成分に含まれる頂点を格納するlistを追加
            if stack[0][0] is not None: # 直前に通った頂点(関節点)が存在するなら
                bcv[idx].append(stack[0][0]) # それを連結成分idxに追加
            while stack:
                pre, now = stack.pop()
                if pre is not None: # 直前に通った辺が存在するなら
                    bce[idx].append((pre, now)) # 通ってきた辺を連結成分idxに追加
                bcv[idx].append(now) # 今いる頂点を連結成分idxに追加
                if now == 0: # 今いる頂点nowが根で
                    if len(self.son[now]) >= 2: # 関節点であるなら
                        for next in self.son[now]:
                            is_ap[now] = True # 関節点であことを記録
                            sub_roots.append((now, next)) # その先は別の連結成分
                        bce.pop() # 「根の関節点のみ」の連結成分は存在しないが追加してしまっているので、例外的に削除する
                        bcv.pop()
                        idx -= 1
                    else: # 関節点でないなら
                        for next in self.son[now]:
                            stack.append((now, next)) # その先は同じ連結成分なのでDFSを続ける
                else: # 根でなく
                    for next in self.son[now]:
                        if self.low[next] >= self.ord[now]: # 子nextに対して関節点なら
                            is_ap[now] = True # 関節点であることを記録
                            sub_roots.append((now, next)) # その先は別の連結成分
                        else: # 関節点でないなら
                            stack.append((now, next)) # その先は同じ連結成分なのでDFSを続ける
                if now == 0 and len(self.son[now]) <= 1:
                    for back in self.back_edge[now]: # 今いる頂点から出る後退辺は同じ連結成分なので
                        bce[idx].append((now, back)) # 連結成分idxに追加
            idx += 1
        return bce, bcv, is_ap

    # block-cut treeを構築
    def block_cut_tree(self):
        bce, bcv, is_ap = self.biconnected_component() # 二重頂点連結成分分解
        num_ap = sum(is_ap) # 関節点の個数
        bc = [[] for _ in range(num_ap+len(bcv))] 
        # bc[i] := block-cut tree上の頂点iに対応する頂点を格納したlist
        # [0:num_ap)は関節点に対応する頂点で、その関節点のみがlistに含まれる
        # [num_ap:len(bc))は連結成分に対応する頂点で、その連結成分から関節点を除いたものがlistに含まれる
        # block-cut tree上の頂点iが関節点に対応している ⇔ i < num_ap
        bc_idx = [None]*self.n
        # bc_idx[i] := (元グラフの)頂点iが属するblock-cut tree上の頂点の番号(bc, bc_treeのindexに対応)
        # 関節点でない頂点iについて、対応するbce, bcvのindexが知りたい場合、bc_idx[i]-num_apで取得可能。
        bc_tree = [[] for _ in range(num_ap+len(bcv))] # bc_tree[i] := block-cut tree上の頂点iの隣接頂点を格納したlist
        idx = 0 # 今見ているblock-cut tree上の頂点番号
        for v in range(self.n): # (元グラフの)各頂点vについて
            if is_ap[v]: # 関節点なら
                bc[idx].append(v) # block-cut tree上の頂点idxにvを対応させる
                bc_idx[v] = idx
                idx += 1
        for bcv_i in bcv: # 各連結成分の
            for v in bcv_i: # 各頂点vについて
                if is_ap[v]: # 関節点なら
                    bc_tree[idx].append(bc_idx[v]) # block-cut tree上の頂点idxと関節点vに対応した頂点を辺で結ぶ
                    bc_tree[bc_idx[v]].append(idx)
                else: # そうでないなら
                    bc[idx].append(v) # block-cut tree上の頂点idxに対応した頂点集合に頂点vを追加
                    bc_idx[v] = idx
            idx += 1
        return bc, bc_idx, bc_tree, num_ap, bce, bcv, is_ap

class HLD:

    # https://github.com/shakayami/ACL-for-python/blob/master/segtree.py
    class segtree():
        n=1
        size=1
        log=2
        d=[0]
        op=None
        e=10**15
        def __init__(self,V,OP,E):
            self.n=len(V)
            self.op=OP
            self.e=E
            self.log=(self.n-1).bit_length()
            self.size=1<<self.log
            self.d=[E for i in range(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)
        def set(self,p,x):
            assert 0<=p and p<self.n
            p+=self.size
            self.d[p]=x
            for i in range(1,self.log+1):
                self.update(p>>i)
        def get(self,p):
            assert 0<=p and p<self.n
            return self.d[p+self.size]
        def prod(self,l,r):
            assert 0<=l and l<=r and r<=self.n
            sml=self.e
            smr=self.e
            l+=self.size
            r+=self.size
            while(l<r):
                if (l&1):
                    sml=self.op(sml,self.d[l])
                    l+=1
                if (r&1):
                    smr=self.op(self.d[r-1],smr)
                    r-=1
                l>>=1
                r>>=1
            return self.op(sml,smr)
        def all_prod(self):
            return self.d[1]
        def max_right(self,l,f):
            assert 0<=l and l<=self.n
            assert f(self.e)
            if l==self.n:
                return self.n
            l+=self.size
            sm=self.e
            while(1):
                while(l%2==0):
                    l>>=1
                if not(f(self.op(sm,self.d[l]))):
                    while(l<self.size):
                        l=2*l
                        if f(self.op(sm,self.d[l])):
                            sm=self.op(sm,self.d[l])
                            l+=1
                    return l-self.size
                sm=self.op(sm,self.d[l])
                l+=1
                if (l&-l)==l:
                    break
            return self.n
        def min_left(self,r,f):
            assert 0<=r and r<=self.n
            assert f(self.e)
            if r==0:
                return 0
            r+=self.size
            sm=self.e
            while(1):
                r-=1
                while(r>1 and (r%2)):
                    r>>=1
                if not(f(self.op(self.d[r],sm))):
                    while(r<self.size):
                        r=(2*r+1)
                        if f(self.op(self.d[r],sm)):
                            sm=self.op(self.d[r],sm)
                            r-=1
                    return r+1-self.size
                sm=self.op(self.d[r],sm)
                if (r& -r)==r:
                    break
            return 0
        def update(self,k):
            self.d[k]=self.op(self.d[2*k],self.d[2*k+1])
        def __str__(self):
            return str([self.get(i) for i in range(self.n)])

    def __init__(self, adj, weights, op, e, root=0) -> None:
        self.n = len(adj)
        self.root = root
        self.parent = [None]*self.n
        stack = [root]
        tps = []
        while stack:
            u = stack.pop()
            tps.append(u)
            for v in adj[u]:
                adj[v].remove(u)
                self.parent[v] = u
                stack.append(v)
        size = [1]*self.n
        heavy = [None]*self.n
        for u in reversed(tps):
            ms = -inf
            for v in adj[u]:
                if size[v] > ms:
                    heavy[u] = v
                    ms = size[v]
                size[u] += size[v]
        del tps, size
        self.idx = [None]*self.n
        self.heavy_root = [None]*self.n
        stack = [(None, root)]
        i = 0
        while stack:
            p, u = stack.pop()
            self.idx[u] = i
            if p is not None:
                self.parent[i] = self.idx[p]
            if self.heavy_root[i] is None:
                self.heavy_root[i] = i
            for v in adj[u]:
                if v == heavy[u]: continue
                stack.append((u, v))
            if heavy[u] is not None:
                self.heavy_root[i+1] = self.heavy_root[i]
                stack.append((u, heavy[u]))
            i += 1
        array = [None]*self.n
        self.vertex = [None]*self.n
        for u, w in enumerate(weights):
            array[self.idx[u]] = w
            self.vertex[self.idx[u]] = u
        self.paths = self.segtree(array, op, e)

    def prod(self, u, v):
        u, v = self.idx[u], self.idx[v]
        ret = self.paths.e
        while self.heavy_root[u] != self.heavy_root[v]:
            if u > v:
                ret = self.paths.op(ret, self.paths.prod(self.heavy_root[u], u+1))
                u = self.parent[self.heavy_root[u]]
            else:
                ret = self.paths.op(ret, self.paths.prod(self.heavy_root[v], v+1))
                v = self.parent[self.heavy_root[v]]
        if u > v: u, v = v, u
        return self.paths.op(ret, self.paths.prod(u, v+1))

    def set(self, u, w):
        self.paths.set(self.idx[u], w)

    def lca(self, u, v):
        u, v = self.idx[u], self.idx[v]
        while self.heavy_root[u] != self.heavy_root[v]:
            if u > v:
                u = self.parent[self.heavy_root[u]]
            else:
                v = self.parent[self.heavy_root[v]]
        return self.vertex[min(u, v)]

    def through(self, u, v, x):
        u, v, x = self.idx[u], self.idx[v], self.idx[x]
        while self.heavy_root[u] != self.heavy_root[v]:
            if u > v:
                if self.heavy_root[u] <= x <= u: return True
                u = self.parent[self.heavy_root[u]]
            else:
                if self.heavy_root[v] <= x <= v: return True
                v = self.parent[self.heavy_root[v]]
        if u > v: u, v = v, u
        return u <= x <= v

N, M, Q = map(int, input().split())
adj = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    adj[a].append(b)
    adj[b].append(a)
ll = LowLink(adj)
tecc, tecc_idx, tecc_tree = ll.two_edge_connected_component()
hld = HLD(tecc_tree, [(-1, i) for i in range(len(tecc))], max, (-inf, -inf))
weights = [[] for _ in range(len(tecc))]

for _ in range(Q):
    q, x, y = map(int, input().split())
    if q == 1:
        u, w = tecc_idx[x-1], y
        heappush(weights[u], -w)
        hld.set(u, (-weights[u][0], u))
    else:
        s, t = tecc_idx[x-1], tecc_idx[y-1]
        ans, u = hld.prod(s, t)
        print(ans)
        if weights[u]:
            heappop(weights[u])
            hld.set(u, (-weights[u][0] if weights[u] else -1, u))
yukicoder

結果

テストケース

ソースコード
