結果

問題 No.3426 Mod K Graph Increments (Hard)
コンテスト
ユーザー mentos_grape
提出日時 2026-01-11 16:07:04
言語 Python3
(3.14.2 + numpy 2.4.0 + scipy 1.16.3)
結果
AC  
実行時間 803 ms / 2,000 ms
コード長 3,232 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,116 ms
コンパイル使用メモリ 20,704 KB
実行使用メモリ 94,296 KB
最終ジャッジ日時 2026-01-11 16:07:09
合計ジャッジ時間 4,419 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

sys.setrecursionlimit(300000)

def main():
    # 入力読み込み
    input = sys.stdin.read
    data = input().split()
    iterator = iter(data)
    
    try:
        num_test_cases = int(next(iterator))
    except StopIteration:
        return

    results = []
    
    for _ in range(num_test_cases):
        try:
            N = int(next(iterator))
            M = int(next(iterator))
            K = int(next(iterator))
        except StopIteration:
            break
        
        # グラフ構築
        adj = [[] for _ in range(N)]
        for _ in range(M):
            u = int(next(iterator)) - 1
            v = int(next(iterator)) - 1
            adj[u].append(v)
            adj[v].append(u)
        
        # 目標値配列 B
        B = []
        for _ in range(N):
            B.append(int(next(iterator)))
        
        # 連結成分ごとの判定
        colors = [-1] * N  # -1:未訪問, 0/1:彩色
        possible = True
        
        for i in range(N):
            if colors[i] != -1:
                continue
            
            # BFSで連結成分の調査と二部グラフ判定を行う
            q = [i]
            colors[i] = 0
            
            sum_c0 = B[i]    # 色0の頂点のBの和
            sum_c1 = 0       # 色1の頂点のBの和
            total_sum = B[i] # 成分全体のBの和
            
            is_bipartite = True
            
            idx = 0
            while idx < len(q):
                u = q[idx]
                idx += 1
                
                c_u = colors[u]
                
                for v in adj[u]:
                    if colors[v] == -1:
                        # 未訪問なら色を塗ってキューに追加
                        colors[v] = 1 - c_u
                        q.append(v)
                        
                        # 和の更新
                        if colors[v] == 0:
                            sum_c0 += B[v]
                        else:
                            sum_c1 += B[v]
                        total_sum += B[v]
                        
                    elif colors[v] == c_u:
                        # 同色が隣接していたら二部グラフではない
                        is_bipartite = False
            
            # 成分ごとの判定ロジック
            if is_bipartite:
                # 二部グラフの場合: (色0の和 - 色1の和) が K の倍数でなければならない
                diff = sum_c0 - sum_c1
                if diff % K != 0:
                    possible = False
                    break
            else:
                # 非二部グラフの場合
                if K % 2 != 0:
                    # Kが奇数なら常に可能（調整可能）
                    pass
                else:
                    # Kが偶数なら、総和が偶数でなければならない
                    if total_sum % 2 != 0:
                        possible = False
                        break
        
        if possible:
            results.append("Yes")
        else:
            results.append("No")

    print('\n'.join(results))

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