結果
問題 |
No.2183 LCA on Rational Tree
|
ユーザー |
![]() |
提出日時 | 2025-06-12 16:44:42 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,128 bytes |
コンパイル時間 | 185 ms |
コンパイル使用メモリ | 82,524 KB |
実行使用メモリ | 180,748 KB |
最終ジャッジ日時 | 2025-06-12 16:44:48 |
合計ジャッジ時間 | 5,323 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 1 TLE * 1 -- * 4 |
ソースコード
import sys import math def main(): input = sys.stdin.read().split() idx = 0 Q = int(input[idx]) idx += 1 for _ in range(Q): p_u = int(input[idx]) q_u = int(input[idx + 1]) p_v = int(input[idx + 2]) q_v = int(input[idx + 3]) idx += 4 # Initial nodes current_u_p, current_u_q = p_u, q_u current_v_p, current_v_q = p_v, q_v path_u = set() path_u.add((current_u_p, current_u_q)) path_v = set() path_v.add((current_v_p, current_v_q)) found = False # Check if initial nodes are common if (current_u_p, current_u_q) in path_v: print(current_u_p, current_u_q) found = True elif (current_v_p, current_v_q) in path_u: print(current_v_p, current_v_q) found = True if not found: while True: # Generate next for u np = current_u_p + 1 nq = current_u_q + 1 g = math.gcd(np, nq) next_u_p = np // g next_u_q = nq // g current_u_p, current_u_q = next_u_p, next_u_q if (current_u_p, current_u_q) in path_v: print(current_u_p, current_u_q) found = True break path_u.add((current_u_p, current_u_q)) # Generate next for v np = current_v_p + 1 nq = current_v_q + 1 g = math.gcd(np, nq) next_v_p = np // g next_v_q = nq // g current_v_p, current_v_q = next_v_p, next_v_q if (current_v_p, current_v_q) in path_u: print(current_v_p, current_v_q) found = True break path_v.add((current_v_p, current_v_q)) # Check if current_u is in path_v # Already checked after adding to path_u if __name__ == '__main__': main()