結果

問題 No.1373 Directed Operations
ユーザー qwewe
提出日時 2025-05-14 13:20:25
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,226 bytes
コンパイル時間 440 ms
コンパイル使用メモリ 82,792 KB
実行使用メモリ 99,120 KB
最終ジャッジ日時 2025-05-14 13:22:00
合計ジャッジ時間 4,468 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# It's good practice to increase recursion limit for DSU in Python for larger N,
# though path compression usually keeps recursion depth low (related to log N).
sys.setrecursionlimit(2 * 10**5) 

def solve():
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))

    parent = list(range(N + 1))
    # is_connected_to_1_comp[i] is true if the component whose root is i, 
    # is connected to node 1's component.
    # This array is indexed by component roots.
    is_connected_to_1_comp = [False] * (N + 1) 
    sz = [1] * (N + 1) # For union-by-size heuristic

    def find(i):
        if parent[i] == i:
            return i
        parent[i] = find(parent[i])
        return parent[i]

    def union_sets(u, v):
        root_u = find(u)
        root_v = find(v)
        if root_u != root_v:
            # Union by size: attach smaller tree under root of larger tree
            if sz[root_u] < sz[root_v]:
                root_u, root_v = root_v, root_u 
            
            parent[root_v] = root_u
            sz[root_u] += sz[root_v]
            
            # If either component was connected to 1, the new merged component is.
            # This property is stored for the new root (root_u).
            is_connected_to_1_comp[root_u] = is_connected_to_1_comp[root_u] or is_connected_to_1_comp[root_v]

    # Initialize component of node 1
    # find(1) will return 1 initially.
    is_connected_to_1_comp[find(1)] = True

    results_x = []

    for op_idx in range(N - 1):
        current_a = A[op_idx]
        # Max x for this operation. x must be at least 1.
        # N - current_a >= N - (N-1) = 1. So limit_x is always >= 1.
        limit_x = N - current_a 

        chosen_x_for_this_op = -1
        
        # Priority 1: Find smallest x in [1, limit_x] that expands reachability
        for x_candidate in range(1, limit_x + 1):
            root_x_cand = find(x_candidate)
            # Target node y = x_candidate + current_a. This is always <= N.
            root_y_cand = find(x_candidate + current_a)

            if is_connected_to_1_comp[root_x_cand] and not is_connected_to_1_comp[root_y_cand]:
                chosen_x_for_this_op = x_candidate
                break
        
        if chosen_x_for_this_op == -1:
            # Priority 2 (Fallback): No Type 1 choice found.
            # Choose x=1. Vertex 1 is always connected to itself.
            # x=1 is always a valid choice for x_candidate since limit_x >= 1.
            chosen_x_for_this_op = 1
            
        results_x.append(chosen_x_for_this_op)
        
        # Perform the operation: add edge and update DSU
        # Edge: chosen_x_for_this_op -> chosen_x_for_this_op + current_a
        union_sets(chosen_x_for_this_op, chosen_x_for_this_op + current_a)

    # Final check: are all nodes connected to 1's component?
    all_reachable = True
    for i in range(1, N + 1):
        if not is_connected_to_1_comp[find(i)]:
            all_reachable = False
            break
            
    if all_reachable:
        sys.stdout.write("YES\n")
        for x_val in results_x:
            sys.stdout.write(str(x_val) + "\n")
    else:
        sys.stdout.write("NO\n")

solve()
0