結果

問題 No.1340 おーじ君をさがせ
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:36:26
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,824 bytes
コンパイル時間 199 ms
コンパイル使用メモリ 82,348 KB
実行使用メモリ 263,408 KB
最終ジャッジ日時 2025-03-20 20:37:43
合計ジャッジ時間 7,684 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 49 TLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    M = int(input[idx]); idx +=1
    T = int(input[idx]); idx +=1

    pre_compute = [0] * N
    for _ in range(M):
        a = int(input[idx]); idx +=1
        b = int(input[idx]); idx +=1
        pre_compute[a] |= (1 << b)

    current = 1 << 0  # initial state: only vertex 0
    if T == 0:
        # No steps, answer is 1
        print(1)
        return

    seen = {}
    history = []
    step = 0
    seen[current] = step
    history.append(current)

    found_cycle = False
    cycle_start = 0
    cycle_length = 0

    while step < T:
        next_nodes = 0
        for v in range(N):
            if (current >> v) & 1:
                next_nodes |= pre_compute[v]
        current = next_nodes
        step += 1

        if current == 0:
            break  # cannot proceed further

        if current in seen:
            prev_step = seen[current]
            cycle_length = step - prev_step
            remaining = T - step
            remaining %= cycle_length
            step = T - remaining
            # Jump to near the end, then simulate remaining steps
            found_cycle = True
            break
        else:
            seen[current] = step
            history.append(current)
            if step == T:
                break

    if not found_cycle:
        # Need to simulate until step reaches T
        while step < T:
            next_nodes = 0
            for v in range(N):
                if (current >> v) & 1:
                    next_nodes |= pre_compute[v]
            current = next_nodes
            step += 1
            if current == 0:
                break

    count = bin(current).count('1') if current != 0 else 0
    print(count)

if __name__ == "__main__":
    main()
0