結果
問題 |
No.2183 LCA on Rational Tree
|
ユーザー |
![]() |
提出日時 | 2025-06-12 18:46:17 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,343 bytes |
コンパイル時間 | 440 ms |
コンパイル使用メモリ | 82,428 KB |
実行使用メモリ | 446,308 KB |
最終ジャッジ日時 | 2025-06-12 18:46:26 |
合計ジャッジ時間 | 4,949 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 1 TLE * 1 -- * 4 |
ソースコード
import math def get_parent(p, q): new_p = p + 1 new_q = q + 1 g = math.gcd(new_p, new_q) return (new_p // g, new_q // g) Q = int(input()) for _ in range(Q): p_u, q_u, p_v, q_v = map(int, input().split()) # Initialize current nodes for u and v current_u = (p_u, q_u) current_v = (p_v, q_v) # Check if they are the same initially if current_u == current_v: print(current_u[0], current_u[1]) continue # Use dictionaries to track visited nodes visited_u = {current_u: True} visited_v = {current_v: True} found = False while not found: # Move u up one step current_u = get_parent(*current_u) if current_u in visited_u: pass # Not necessary as each node has a unique path visited_u[current_u] = True # Check if current_u is in visited_v if current_u in visited_v: print(current_u[0], current_u[1]) found = True break # Move v up one step current_v = get_parent(*current_v) if current_v in visited_v: pass visited_v[current_v] = True # Check if current_v is in visited_u if current_v in visited_u: print(current_v[0], current_v[1]) found = True break