結果

問題 No.2183 LCA on Rational Tree
ユーザー gew1fw
提出日時 2025-06-12 13:31:18
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,343 bytes
コンパイル時間 179 ms
コンパイル使用メモリ 82,180 KB
実行使用メモリ 245,144 KB
最終ジャッジ日時 2025-06-12 13:36:45
合計ジャッジ時間 5,859 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 TLE * 1 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

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
0