結果

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

ソースコード

diff #
raw source code 

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()
0