結果

問題 No.3580 二成分の和
コンテスト
ユーザー LyricalMaestro
提出日時 2026-07-05 16:40:51
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 161 ms / 2,000 ms
コード長 3,285 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,266 ms
コンパイル使用メモリ 95,592 KB
実行使用メモリ 85,400 KB
最終ジャッジ日時 2026-07-05 16:42:56
合計ジャッジ時間 8,609 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# https://yukicoder.me/problems/no/3580

from collections import deque

class UnionFind:
    """
    UnionFindの基本的な処理を実装したクラス
    """

    def __init__(self, size):
        self.root = [i for i in range(size)]
        self.size = [1] * size

    def get_root(self, v):
        if v == self.root[v]:
            return v
        else:
            old_root = self.root[v]
            new_root = self.get_root(old_root)
            self.root[v] = new_root
            return new_root

    def merge(self, u, v):
        root_u = self.get_root(u)
        root_v = self.get_root(v)
        if root_u == root_v:
            return False

        if self.size[root_u] >= self.size[root_v]:
            self.size[root_u] += self.size[root_v]
            self.root[root_v] = root_u
            self.root[v] = root_u
        else:
            self.size[root_v] += self.size[root_u]
            self.root[root_u] = root_v
            self.root[u] = root_v
        return True
    

def main():
    N, M, B = map(int, input().split())
    conditions = []
    for _ in range(M):
        i, j, c = map(int, input().split())
        conditions.append((i - 1, j - 1, c))
    
    # グラフの問題として見た時の連結成分を考慮する
    uf = UnionFind(N)
    for i, j, _ in conditions:
        uf.merge(i, j)
    r_map = {}
    for i in range(N):
        r_i = uf.get_root(i)
        if r_i not in r_map:
            r_map[r_i] = [[], []]
        r_map[r_i][0].append(i)
    for i, j, c in conditions:
        r_i = uf.get_root(i)
        r_map[r_i][1].append((i, j, c))
    
    answer_map_list = []
    for nodes, edges in r_map.values():
        next_nodes = {n : [] for n in nodes}
        for i, j, c in edges:
            next_nodes[i].append((j, c))
            next_nodes[j].append((i, c))

        queue = deque()
        start_n = list(nodes)[0]
        queue.append(start_n)
        coefs = {start_n: (0, 1)}
        while len(queue) > 0:
            v = queue.popleft()

            intercepts_v, c_v = coefs[v]
            for w, c in next_nodes[v]:
                if w not in coefs:
                    new_c_v = (-1) * c_v
                    new_intercepts = c - intercepts_v
                    coefs[w] = (new_intercepts, new_c_v)
                    queue.append(w)
        
        # start_nの値を動かしていく
        exists = False
        answer_values = {}
        for start_b_n in range(B):
            value_map = {}
            for n in nodes:
                i, c = coefs[n]
                x = i - c * start_b_n
                x %= B
                value_map[n] = x
            
            is_ok = True
            for i, j, c in edges:
                if (value_map[i] + value_map[j] - c) % B != 0:
                    is_ok = False
            
            if is_ok:
                exists = True
                answer_values = value_map
                break
        if not exists:
            print("No")
            return
        answer_map_list.append(answer_values)
    

    answer = [0] * N
    for answer_values in answer_map_list:
        for n, v in answer_values.items():
            answer[n] = v
    print("Yes")
    print(" ".join(map(str, answer)))









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