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

• 問題: No.529 帰省ラッシュ
• ユーザー: toyuzuko
• 提出日時: 2020-05-19 22:39:52
• 言語: PyPy3 (7.3.15)
• 結果: WA
• 実行時間: -
• コード長: 8,086 bytes
• コンパイル時間: 329 ms
• コンパイル使用メモリ: 82,312 KB
• 実行使用メモリ: 202,900 KB
• 最終ジャッジ日時: 2024-10-01 23:09:05
• 合計ジャッジ時間: 19,400 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	42 ms; 57,548 KB
testcase_01	AC	42 ms; 56,568 KB
testcase_02	AC	43 ms; 57,412 KB
testcase_03	AC	43 ms; 56,868 KB
testcase_04	AC	177 ms; 79,808 KB
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	AC	1,139 ms; 166,796 KB
testcase_13	AC	879 ms; 197,020 KB
testcase_14	AC	924 ms; 176,728 KB
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	AC	1,480 ms; 201,620 KB
testcase_19	AC	1,503 ms; 202,220 KB

ソースコード

from heapq import heappop,heappush,heapify
from collections import deque

class Graph(): #non-directed
    def __init__(self,n,edge):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]
        for e in edge:
            self.graph[e[0] - 1].append(e[1] - 1)
            self.graph[e[1] - 1].append(e[0] - 1)
            self.deg[e[0] - 1] += 1
            self.deg[e[1] - 1] += 1

    def lowlink(self): #DFS木, ord, lowを計算
        self.ord = [None for _ in range(self.n)]
        self.low = [None for _ in range(self.n)]
        self.group = [None for _ in range(self.n)]
        self.prev = [None for _ in range(self.n)]
        self.tree = [[] for _ in range(self.n)]
        self.sorted = []
        order = 0
        count = 0
        low = [None for _ in range(self.n)]
        for s in range(self.n):
            if self.group[s] is None:
                stack = [(s, None)]
                while stack:
                    node, par = stack.pop()
                    if self.group[node] is None:
                        self.group[node] = count
                        self.ord[node] = order
                        self.sorted.append(node)
                        order += 1
                        if par is not None:
                            self.prev[node] = par
                            self.tree[par].append(node)
                        for adj in self.graph[node]:
                            if self.group[adj] is None:
                                stack.append((adj, node))
                count += 1
        for node in self.sorted[::-1]:
            self.low[node] = self.ord[node]
            for adj in self.graph[node]:
                if self.prev[adj]  == node:
                    self.low[node] = min(self.low[node], self.low[adj])
                elif self.prev[node] == adj:
                    continue
                else:
                    self.low[node] = min(self.low[node], self.ord[adj])

    def articulation(self):
        res = []
        for node in range(self.n):
            if self.prev[node] is None and len(self.tree[node]) > 1:
                res.append(node)
            if self.prev[node] is not None:
                for adj in self.tree[node]:
                    if self.ord[node] <= self.low[adj]:
                        res.append(node)
                        break
        return res

    def bridge(self):
        res = []
        for node in range(self.n):
            for adj in self.tree[node]:
                if self.ord[node] < self.low[adj]:
                    res.append((node, adj))
        return res

class Tree():
    def __init__(self, n, edge):
        self.n = n
        self.tree = [[] for _ in range(n)]
        for e in edge:
            self.tree[e[0] - 1].append(e[1] - 1)
            self.tree[e[1] - 1].append(e[0] - 1)

    def setroot(self, root):
        self.root = root
        self.parent = [None for _ in range(self.n)]
        self.parent[root] = -1
        self.depth = [None for _ in range(self.n)]
        self.depth[root] = 0
        self.order = []
        self.order.append(root)
        self.size = [1 for _ in range(self.n)]
        stack = [root]
        while stack:
            node = stack.pop()
            for adj in self.tree[node]:
                if self.parent[adj] is None:
                    self.parent[adj] = node
                    self.depth[adj] = self.depth[node] + 1
                    self.order.append(adj)
                    stack.append(adj)
        for node in self.order[::-1]:
            for adj in self.tree[node]:
                if self.parent[node] == adj:
                    continue
                self.size[node] += self.size[adj]

    def heavylight_decomposition(self):
        self.order = [None for _ in range(self.n)]
        self.head = [None for _ in range(self.n)]
        self.head[self.root] = self.root
        self.next = [None for _ in range(self.n)]
        stack = [self.root]
        order = 0
        while stack:
            node = stack.pop()
            self.order[node] = order
            order += 1
            maxsize = 0
            for adj in self.tree[node]:
                if self.parent[node] == adj:
                    continue
                if maxsize < self.size[adj]:
                    maxsize = self.size[adj]
                    self.next[node] = adj
            for adj in self.tree[node]:
                if self.parent[node] == adj or self.next[node] == adj:
                    continue
                self.head[adj] = adj
                stack.append(adj)
            if self.next[node] is not None:
                self.head[self.next[node]] = self.head[node]
                stack.append(self.next[node])

    def range_hld(self, u, v, edge=False):
        res = []
        while True:
            if self.order[u] > self.order[v]: u, v = v, u
            if self.head[u] != self.head[v]:
                res.append((self.order[self.head[v]], self.order[v] + 1))
                v = self.parent[self.head[v]]
            else:
                res.append((self.order[u] + edge, self.order[v] + 1))
                return res

    def subtree_hld(self, u):
        return self.order[u], self.order[u] + self.size[u]

    def lca_hld(self, u, v):
        while True:
            if self.order[u] > self.order[v]: u, v = v, u
            if self.head[u] != self.head[v]:
                v = self.parent[self.head[v]]
            else:
                return u

class SegmentTree():
    def __init__(self, arr, func=min, ie=2**63):
        self.h = (len(arr) - 1).bit_length()
        self.n = 2**self.h
        self.ie = ie
        self.func = func
        self.tree = [ie for _ in range(2 * self.n)]
        for i in range(len(arr)):
            self.tree[self.n + i] = arr[i]
        for i in range(1, self.n)[::-1]:
            self.tree[i] = func(self.tree[2 * i], self.tree[2 * i + 1])

    def set(self, idx, x):
        idx += self.n
        self.tree[idx] = x
        while idx:
            idx >>= 1
            self.tree[idx] = self.func(self.tree[2 * idx], self.tree[2 * idx + 1])

    def query(self, lt, rt):
        lt += self.n
        rt += self.n
        vl = vr = self.ie
        while rt - lt > 0:
            if lt & 1:
                vl = self.func(vl, self.tree[lt])
                lt += 1
            if rt & 1:
                rt -= 1
                vr = self.func(self.tree[rt], vr)
            lt >>= 1
            rt >>= 1
        return self.func(vl, vr)

import sys
input = sys.stdin.readline

INF = 10**18

N, M, Q = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(M)]

g = Graph(N, edge)
g.lowlink()
bridge = set(g.bridge())
edge_no_bridge = []

for e in edge:
    if (e[0] - 1, e[1] - 1) in bridge or (e[1] - 1, e[0] - 1) in bridge:
        continue
    edge_no_bridge.append(e)

graph_no_edge = Graph(N, edge_no_bridge)
graph_no_edge.lowlink()
decomposed = graph_no_edge.group
count = max(decomposed) + 1
decomposed_to_node = [[] for _ in range(count)]

for i in range(count):
    decomposed_to_node[decomposed[i]].append(i)

branch = []

for a, b in bridge:
    branch.append((decomposed[a] + 1, decomposed[b] + 1))

t = Tree(count, branch)
t.setroot(0)
t.heavylight_decomposition()

arr = [(-1, t.order[i]) for i in range(count)]
st = SegmentTree(arr, max, (-INF, -INF))

enemy = [[] for _ in range(count)]
res = []

for _ in range(Q):
    q, x, y = map(int, input().split())
    if q == 1:
        heappush(enemy[decomposed[x - 1]], -y)
        st.set(t.order[decomposed[x - 1]], (-enemy[decomposed[x - 1]][0], decomposed[x - 1]))
    else:
        tmp = (-1, -INF)
        for lt, rt in t.range_hld(decomposed[x - 1], decomposed[y - 1]):
            tmp = max(tmp, st.query(lt, rt))
        value, idx = tmp
        res.append(value)
        if enemy[idx]:
            heappop(enemy[idx])
        if enemy[idx]:
            st.set(t.order[idx], (-enemy[idx][0], idx))
        else:
            st.set(t.order[idx], (-1, idx))

print('\n'.join(map(str, res)))