結果
問題 |
No.2183 LCA on Rational Tree
|
ユーザー |
![]() |
提出日時 | 2025-04-16 00:06:54 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 774 bytes |
コンパイル時間 | 460 ms |
コンパイル使用メモリ | 81,952 KB |
実行使用メモリ | 67,768 KB |
最終ジャッジ日時 | 2025-04-16 00:08:26 |
合計ジャッジ時間 | 3,923 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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)