結果

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

ソースコード

diff # 

def main():
    import sys
    n, m, T = map(int, sys.stdin.readline().split())
    adj = [set() for _ in range(n)]
    for _ in range(m):
        a, b = map(int, sys.stdin.readline().split())
        adj[a].add(b)
    
    steps = [ {0} ]
    seen = {}
    mask = 1 << 0
    seen[mask] = 0  # steps[0] is after 0 moves
    
    for t in range(1, T + 1):
        current_set = steps[-1]
        new_set = set()
        for u in current_set:
            if len(adj[u]) == 0:
                # If any vertex has no outgoing edges, it leads to disappearance
                # But we process all possible in the current step
                # So if u has no adj, then none added from u
                continue
            for v in adj[u]:
                new_set.add(v)
        # Check if new_set is empty
        if not new_set:
            print(0)
            return
        # Calculate mask
        mask = 0
        for v in new_set:
            mask |= 1 << v
        # Check if mask exists in seen
        if mask in seen:
            prev_step = seen[mask]
            cycle_length = t - prev_step
            remaining = T - prev_step
            remainder = remaining % cycle_length
            final_step = prev_step + remainder
            print(len(steps[final_step]))
            return
        else:
            # Check if new_set is same as last step
            if steps and new_set == steps[-1]:
                print(len(new_set))
                return
            seen[mask] = t
            steps.append(new_set)
    # After all steps simulated
    print(len(steps[-1]))

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