結果

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

ソースコード

diff # 

def main():
    import sys
    N, M, T = map(int, sys.stdin.readline().split())
    edges = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, sys.stdin.readline().split())
        edges[a].append(b)
    
    if T == 0:
        print(1)
        return
    
    out_degree = [len(es) for es in edges]
    if out_degree[0] == 0:
        print(0)
        return
    
    # Precompute the mask for each vertex u: pre[u] is the mask of reachable vertices in one step
    pre = [0] * N
    for u in range(N):
        if out_degree[u] == 0:
            pre[u] = 0
        else:
            mask = 0
            for v in edges[u]:
                mask |= 1 << v
            pre[u] = mask
    
    current_mask = 1 << 0  # initial mask is only vertex 0
    history = {current_mask: 0}
    masks = [current_mask]
    step = 0
    found_cycle = False
    cycle_start = 0
    cycle_length = 0
    
    while step < T:
        new_mask = 0
        mask = current_mask
        while mask:
            lsb = mask & -mask
            u = (lsb).bit_length() - 1
            new_mask |= pre[u]
            mask ^= lsb
        
        step += 1
        current_mask = new_mask
        if current_mask in history:
            # Found a cycle
            cycle_start = history[current_mask]
            cycle_length = step - cycle_start
            found_cycle = True
            break
        history[current_mask] = step
        masks.append(current_mask)
        if current_mask == 0:
            break  # No further steps possible
    
    if found_cycle:
        remaining_steps = T - cycle_start
        remaining = remaining_steps % cycle_length
        final_step = cycle_start + remaining
        if final_step < len(masks):
            current_mask = masks[final_step]
        else:
            idx_in_cycle = (final_step - cycle_start) % cycle_length
            current_mask = masks[cycle_start + idx_in_cycle]
    elif step < T:
        # This means current_mask became 0 before T steps
        pass
    
    print(bin(current_mask).count('1'))

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