結果

問題 No.2183 LCA on Rational Tree
ユーザー lam6er
提出日時 2025-04-16 00:08:55
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 756 bytes
コンパイル時間 432 ms
コンパイル使用メモリ 81,900 KB
実行使用メモリ 437,724 KB
最終ジャッジ日時 2025-04-16 00:09:48
合計ジャッジ時間 5,029 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 TLE * 1 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
import math

def compute_parent(a, b):
    a_plus_1 = a + 1
    b_plus_1 = b + 1
    g = math.gcd(a_plus_1, b_plus_1)
    return (a_plus_1 // g, b_plus_1 // g)

def find_lca(p1, q1, p2, q2):
    visited_u = dict()
    visited_v = dict()
    u = (p1, q1)
    v = (p2, q2)
    while True:
        if u in visited_v:
            return u
        if v in visited_u:
            return v
        if u == v:
            return u
        visited_u[u] = True
        visited_v[v] = True
        # Compute parents
        u = compute_parent(*u)
        v = compute_parent(*v)

Q = int(sys.stdin.readline())
for _ in range(Q):
    p_u, q_u, p_v, q_v = map(int, sys.stdin.readline().split())
    lca = find_lca(p_u, q_u, p_v, q_v)
    print(lca[0], lca[1])
0