結果
問題 | 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 |
ソースコード
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)