結果

問題 No.3425 Mod K Graph Increments (Easy)
コンテスト
ユーザー koheijkt
提出日時 2026-01-11 14:45:18
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 212 ms / 2,000 ms
コード長 2,030 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 314 ms
コンパイル使用メモリ 82,336 KB
実行使用メモリ 79,372 KB
最終ジャッジ日時 2026-01-11 14:45:21
合計ジャッジ時間 2,767 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys, math
sys.setrecursionlimit(10**8)
sys.set_int_max_str_digits(0)
INF = 1e18
MOD = 998244353
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import product, combinations, permutations, groupby, accumulate
from heapq import heapify, heappop, heappush
def I():   return sys.stdin.readline().rstrip()
def II():  return int(sys.stdin.readline().rstrip())
def IS():  return sys.stdin.readline().rstrip().split()
def MII(): return map(int, sys.stdin.readline().rstrip().split())
def LI():  return list(sys.stdin.readline().rstrip())
def TII(): return tuple(map(int, sys.stdin.readline().rstrip().split()))
def LII(): return list(map(int, sys.stdin.readline().rstrip().split()))
def LSI(): return list(map(str, sys.stdin.readline().rstrip().split()))
def GMI(): return list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))
def kiriage(a, b): return (a+b-1)//b
def chmax(DP,i,v):
    if DP[i] < v: DP[i] = v
def chmin(DP,i,v):
    if DP[i] > v: DP[i] = v

T = II()

for i in range(T):
    N, M, K = MII()
    G = [set() for _ in range(N)]
    jisu = [0] * (N)
    for i in range(M):
        u, v = MII()
        u -= 1
        v -= 1
        G[u].add(v)
        G[v].add(u)
        jisu[u] += 1
        jisu[v] += 1

    A = [0] * N
    B = LII()

    # 最初だけ全探索し、尻尾を捕まえる
    jisu1 = [] # stack でなくて que でやってもよい

    for i in range(N):
        if jisu[i] == 1:
            jisu1.append(i)

    while len(jisu1) > 1:
        pos = jisu1.pop()
        # pos から行ける頂点の入次数を1減らす
        nex = G[pos].pop()
        jisu[nex] -= 1
        # nex で帳尻をあわせる
        diff = (B[pos] - A[pos])%K            
        A[pos] = B[pos]
        # diff を nex にも押し付ける
        A[nex] = (A[nex] + diff)%K
        if jisu[nex] == 1:
            jisu1.append(nex)
        G[nex].remove(pos)

    if A == B:
        print('Yes')
    else:
        print('No')
0