結果

問題 No.3104 Simple Graph Problem
コンテスト
ユーザー ゼット
提出日時 2025-04-11 23:06:30
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 697 ms / 2,000 ms
コード長 1,747 bytes
コンパイル時間 600 ms
コンパイル使用メモリ 82,968 KB
実行使用メモリ 116,424 KB
最終ジャッジ日時 2025-04-11 23:06:57
合計ジャッジ時間 23,268 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 65
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

class unif:
  def __init__(self,n):
    self.pare=[-1]*n
    self.size=[1]*n
  def root(self,x):
    while self.pare[x]!=-1:
      x=self.pare[x]
    return x
  def unite(self,u,v):
    rootu=self.root(u)
    rootv=self.root(v)
    if rootu!=rootv:
      if self.size[rootu]>=self.size[rootv]:
        self.pare[rootv]=rootu
        self.size[rootu]+=self.size[rootv]
      else:
        self.pare[rootu]=rootv
        self.size[rootv]+=self.size[rootu]
  def same(self,s,t):
    return self.root(s)==self.root(t)
N,M=map(int,input().split())
T=[]
B=list(map(int,input().split()))
G=[[] for i in range(N)]
L=[]
Z=unif(N)
for i in range(M):
  a,b=map(int,input().split())
  a-=1
  b-=1
  if Z.same(a,b)==False:
    G[a].append((b,i))
    G[b].append((a,i))
    Z.unite(a,b)
  L.append((a,b))
result=[0]*M
from collections import deque
S=deque()
dist=[-1]*N
dist[0]=0
S.append(0)
while S:
  x=S.popleft()
  for E in G[x]:
    y=E[0]
    if dist[y]>=0:
      continue
    dist[y]=dist[x]+1
    S.append(y)
mod=998244353
z=0
for i in range(1,N):
  if dist[i]%2==1:
    z+=B[i]
  else:
    z-=B[i]
c=z-B[0]
dp=[0]*N
z=c
for i in range(M):
  a,b=L[i][:]
  if dist[a]%2==dist[b]%2:
    if dist[a]%2==1:
      k=z*pow(2,-1,mod)
      k%=mod
      result[i]=k
      dp[a]+=k
      dp[b]+=k
      break
    else:
      k=(-z)*pow(2,-1,mod)
      k%=mod
      result[i]=k
      dp[a]+=k
      dp[b]+=k
      break
P=[]
for i in range(N):
  P.append((dist[i],i))
P.sort(reverse=True)
for i in range(N):
  pos=P[i][1]
  for E in G[pos]:
    y,t=E[:]
    if dist[y]<dist[pos]:
      continue
    h=B[y]-dp[y]
    h%=mod
    result[t]=h
    dp[y]+=h
    dp[pos]+=h
    dp[y]%=mod
    dp[pos]%=mod
if dp[0]!=B[0]:
  print(-1)
else:
  print(*result)
0