結果
問題 |
No.2183 LCA on Rational Tree
|
ユーザー |
![]() |
提出日時 | 2025-04-16 16:33:28 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 774 bytes |
コンパイル時間 | 600 ms |
コンパイル使用メモリ | 82,472 KB |
実行使用メモリ | 68,504 KB |
最終ジャッジ日時 | 2025-04-16 16:36:12 |
合計ジャッジ時間 | 4,187 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 1 TLE * 1 -- * 4 |
ソースコード
import math def compute_base(p, q): d = q - p while d > 1: g = math.gcd(p + 1, q + 1) new_p = (p + 1) // g new_q = (q + 1) // g p, q = new_p, new_q d = q - p return (p, q) Q = int(input()) for _ in range(Q): p1, q1, p2, q2 = map(int, input().split()) # Compute base nodes base1_p, base1_q = compute_base(p1, q1) base2_p, base2_q = compute_base(p2, q2) # Compare the base nodes if (base1_p, base1_q) == (base2_p, base2_q): l_p, l_q = base1_p, base1_q else: # In the difference 1 phase, the LCA is the one with larger p if base1_p > base2_p: l_p, l_q = base1_p, base1_q else: l_p, l_q = base2_p, base2_q print(l_p, l_q)