結果

問題 No.2296 Union Path Query (Hard)
ユーザー t98slidert98slider
提出日時 2023-03-16 19:57:50
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,573 ms / 7,000 ms
コード長 3,810 bytes
コンパイル時間 497 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 186,632 KB
最終ジャッジ日時 2024-05-02 14:19:11
合計ジャッジ時間 77,646 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 49 ms
54,784 KB
testcase_01 AC 101 ms
112,768 KB
testcase_02 AC 101 ms
113,024 KB
testcase_03 AC 101 ms
113,024 KB
testcase_04 AC 2,088 ms
169,432 KB
testcase_05 AC 2,059 ms
168,932 KB
testcase_06 AC 2,531 ms
177,396 KB
testcase_07 AC 1,522 ms
165,600 KB
testcase_08 AC 1,519 ms
166,952 KB
testcase_09 AC 1,343 ms
134,760 KB
testcase_10 AC 1,382 ms
136,760 KB
testcase_11 AC 1,468 ms
136,220 KB
testcase_12 AC 1,514 ms
132,092 KB
testcase_13 AC 633 ms
86,764 KB
testcase_14 AC 530 ms
83,512 KB
testcase_15 AC 2,573 ms
178,320 KB
testcase_16 AC 2,215 ms
158,060 KB
testcase_17 AC 1,504 ms
112,840 KB
testcase_18 AC 2,327 ms
175,600 KB
testcase_19 AC 1,633 ms
133,104 KB
testcase_20 AC 2,257 ms
173,592 KB
testcase_21 AC 2,017 ms
167,460 KB
testcase_22 AC 2,167 ms
170,352 KB
testcase_23 AC 651 ms
186,632 KB
testcase_24 AC 545 ms
131,428 KB
testcase_25 AC 1,372 ms
169,012 KB
testcase_26 AC 1,353 ms
169,036 KB
testcase_27 AC 2,151 ms
168,848 KB
testcase_28 AC 2,170 ms
169,612 KB
testcase_29 AC 2,299 ms
171,476 KB
testcase_30 AC 2,296 ms
171,784 KB
testcase_31 AC 2,206 ms
155,280 KB
testcase_32 AC 2,150 ms
155,268 KB
testcase_33 AC 1,968 ms
152,968 KB
testcase_34 AC 1,621 ms
150,280 KB
testcase_35 AC 1,481 ms
149,816 KB
testcase_36 AC 1,264 ms
144,144 KB
testcase_37 AC 2,034 ms
135,188 KB
testcase_38 AC 2,064 ms
135,060 KB
testcase_39 AC 2,049 ms
134,296 KB
testcase_40 AC 2,109 ms
135,064 KB
testcase_41 AC 48 ms
54,784 KB
testcase_42 AC 48 ms
54,528 KB
testcase_43 AC 48 ms
54,656 KB
testcase_44 AC 1,103 ms
181,948 KB
testcase_45 AC 1,120 ms
173,752 KB
testcase_46 AC 1,252 ms
168,816 KB
testcase_47 AC 1,493 ms
172,020 KB
testcase_48 AC 1,298 ms
169,860 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from sys import stdin
from collections import deque

class UnionFind():
    def __init__(self, n):
        self.parent_or_size = [-1] * n
        self.G = [[] for i in range(n)]
        self.E = [[] for i in range(n)]
        self.depth = [0] * n
        self.dp = [0] * n
        self.log_table = [0] * n
        self.diameter = [0] * n
        self.diameter_vertex = [0] * (2 * n)
        self.parent = [[-1] * n for i in range(18)]
        self.que = deque()

        for i in range(n):
            self.diameter_vertex[i << 1] = i
            self.diameter_vertex[(i << 1) + 1] = i
        for i in range(2, n):
            self.log_table[i] = self.log_table[i >> 1] + 1


    def leader(self, x):
        return x if self.parent_or_size[x] < 0 else self.parent_or_size[x]

    def merge(self, u, v, w):
        x, y = self.leader(u), self.leader(v)
        if -self.parent_or_size[x] < -self.parent_or_size[y]: 
            x, y = y, x
            u, v = v, u
        
        self.parent_or_size[x] += self.parent_or_size[y]
        self.G[u].append(v)
        self.G[v].append(u)
        self.E[v].append(w)
        self.E[u].append(w)
        self.update_parent(v, u, w)

        self.que.append(v)
        while len(self.que):
            v = self.que.popleft()
            self.parent_or_size[v] = x
            for i in range(len(self.G[v])):
                if self.G[v][i] == self.parent[0][v]: continue
                self.update_parent(self.G[v][i], v, self.E[v][i])
                self.que.append(self.G[v][i])

        self.update_diameter(x, y)
        

    def update_parent(self, v, par, w):
        logv = self.log_table[max(self.depth[v], self.depth[par] + 1)]
        self.depth[v] = self.depth[par] + 1
        self.dp[v] = self.dp[par] + w
        self.parent[0][v] = par
        for i in range(logv):
            self.parent[i + 1][v] = -1 if self.parent[i][v] == -1 else self.parent[i][self.parent[i][v]]

    def update_diameter(self, x, y):
        mx, v, u = 0, 0, 0
        v1, v2 = self.diameter_vertex[2 * x], self.diameter_vertex[2 * x + 1]
        v3, v4 = self.diameter_vertex[2 * y], self.diameter_vertex[2 * y + 1]
        if self.diameter[x] >= self.diameter[y]:
            mx, u, v = self.diameter[x], v1, v2
        else:
            mx, u, v = self.diameter[y], v3, v4
        
        d = self.dist(v1, v3)
        if d > mx: mx, u, v = d, v1, v3
        d = self.dist(v1, v4)
        if d > mx: mx, u, v = d, v1, v4
        d = self.dist(v2, v3)
        if d > mx: mx, u, v = d, v2, v3
        d = self.dist(v2, v4)
        if d > mx: mx, u, v = d, v2, v4

        self.diameter[x], self.diameter_vertex[2 * x], self.diameter_vertex[2 * x + 1] = mx, u, v
    
    def dist(self, u, v):
        if self.leader(u) != self.leader(v): return -1
        if self.depth[u] > self.depth[v]: u, v = v, u
        res = self.dp[u] + self.dp[v]
        d = self.depth[v] - self.depth[u]

        for i in range(self.log_table[d] + 1):
            if d >> i & 1: v = self.parent[i][v]
        
        if u == v: return res - 2 * self.dp[v]

        for i in range(self.log_table[self.depth[v]], -1, -1):
            if self.parent[i][v] != self.parent[i][u]:
                u = self.parent[i][u]
                v = self.parent[i][v]
        
        return res - 2 * self.dp[self.parent[0][v]]
        

N, X, Q = map(int, stdin.readline().split())

uf = UnionFind(N)

for _ in range(Q):
    query = list(map(int, stdin.readline().split()))
    if query[0] == 1:
        uf.merge(X, query[1], query[2])
    elif query[0] == 2:
        d = uf.dist(query[1], query[2])
        print(d)
        if d != -1: 
            X += d
            X %= N
    elif query[0] == 3:
        print(uf.diameter[uf.leader(query[1])])
    else:
        X += query[1]
        if X >= N: X -= N
0