結果
問題 |
No.2295 Union Path Query (Medium)
|
ユーザー |
|
提出日時 | 2025-03-11 00:06:12 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,513 ms / 4,000 ms |
コード長 | 3,716 bytes |
コンパイル時間 | 586 ms |
コンパイル使用メモリ | 82,364 KB |
実行使用メモリ | 255,584 KB |
最終ジャッジ日時 | 2025-03-11 00:07:24 |
合計ジャッジ時間 | 66,791 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 53 |
ソースコード
## https://yukicoder.me/problems/no/2295 MOD = 998244353 class UnionFind: """ UnionFindの基本的な処理を実装したクラス """ def __init__(self, size): self.root = [i for i in range(size)] self.size = [1] * size def get_root(self, v): if v == self.root[v]: return v else: old_root = self.root[v] new_root = self.get_root(old_root) self.root[v] = new_root return new_root def merge(self, u, v): root_u = self.get_root(u) root_v = self.get_root(v) if root_u == root_v: return False if self.size[root_u] >= self.size[root_v]: self.size[root_u] += self.size[root_v] self.root[root_v] = root_u self.root[v] = root_u else: self.size[root_v] += self.size[root_u] self.root[root_u] = root_v self.root[u] = root_v return True def main(): N, X0, Q = map(int, input().split()) queries = [] for _ in range(Q): values = tuple(map(int, input().split())) queries.append(values) # 下準備1 uf = UnionFind(N) root_3_values = [0] * N belong_v_list = [[i] for i in range(N)] root_history = [[(i, 0)] for i in range(N)] x = X0 # クエリを捌いていく for values in queries: if values[0] == 4: _, value = values x += value x %= N elif values[0] == 1: _, v, w = values root_v = uf.get_root(v) size_v = uf.size[root_v] root_x = uf.get_root(x) size_x = uf.size[root_x] if uf.merge(root_v, root_x): d = (size_v * size_x) % MOD d *= w d %= MOD new_root_x = uf.get_root(x) old_root = root_v if new_root_x == root_x else root_x root_3_values[new_root_x] += root_3_values[old_root] root_3_values[new_root_x] %= MOD root_3_values[new_root_x] += d root_3_values[new_root_x] %= MOD for a in belong_v_list[old_root]: belong_v_list[new_root_x].append(a) root_history[a].append((new_root_x, w)) elif values[0] == 3: _, v = values root_v = uf.get_root(v) print(root_3_values[root_v]) elif values[0] == 2: _, u, v = values if root_history[u][-1][0] != root_history[v][-1][0]: print(-1) else: if len(root_history[u]) > len(root_history[v]): u, v = v, u # len(root_history[u]) <= len(root_histroy[v])としても一般性を失わない d_u = len(root_history[u]) d_v = len(root_history[v]) diff = d_v - d_u low = 0 high = d_u - 1 while high - low > 1: mid = (high + low) // 2 if root_history[u][mid][0] == root_history[v][diff + mid][0]: high = mid else: low = mid if root_history[u][low][0] == root_history[v][diff + low][0]: ans = low else: ans = high ans1 = root_history[u][ans][1] ans2 = root_history[v][diff + ans][1] ans = max(ans1, ans2) print(ans) x += ans x %= N if __name__ == "__main__": main()