結果
問題 |
No.2183 LCA on Rational Tree
|
ユーザー |
![]() |
提出日時 | 2025-04-16 00:07:22 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 756 bytes |
コンパイル時間 | 175 ms |
コンパイル使用メモリ | 81,544 KB |
実行使用メモリ | 437,756 KB |
最終ジャッジ日時 | 2025-04-16 00:08:38 |
合計ジャッジ時間 | 4,733 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 1 TLE * 1 -- * 4 |
ソースコード
import sys import math def compute_parent(a, b): a_plus_1 = a + 1 b_plus_1 = b + 1 g = math.gcd(a_plus_1, b_plus_1) return (a_plus_1 // g, b_plus_1 // g) def find_lca(p1, q1, p2, q2): visited_u = dict() visited_v = dict() u = (p1, q1) v = (p2, q2) while True: if u in visited_v: return u if v in visited_u: return v if u == v: return u visited_u[u] = True visited_v[v] = True # Compute parents u = compute_parent(*u) v = compute_parent(*v) Q = int(sys.stdin.readline()) for _ in range(Q): p_u, q_u, p_v, q_v = map(int, sys.stdin.readline().split()) lca = find_lca(p_u, q_u, p_v, q_v) print(lca[0], lca[1])