結果

問題 No.2494 Sum within Components
コンテスト
ユーザー vjudge1
提出日時 2025-11-20 16:58:10
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,715 bytes
コンパイル時間 309 ms
コンパイル使用メモリ 82,104 KB
実行使用メモリ 247,956 KB
最終ジャッジ日時 2025-11-20 16:58:19
合計ジャッジ時間 8,886 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 TLE * 2 -- * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

class DSU:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.c = [i for i in range(n)]
        
    def find(self, i):
        if self.p[i] != i:
            return self.find(self.p[i])
        
        return i
    
    def union(self, i, j):
        i = self.find(i)
        j = self.find(j)
        
        if i == j: return
        
        self.p[j] = i
        while self.c[i] != i:
            i = self.c[i]
        self.c[i] = j
        
    def extract(self, i):
        s = set()
        s.add(i)
        while self.c[i] != i:
            i = self.c[i]
            s.add(i)
            
        return frozenset(s)
            
import sys
import math
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations
from collections import Counter, defaultdict, deque
from heapq import heappush, heappop

# ---------- FAST IO ----------
input = lambda: sys.stdin.readline().strip()
def read_int(): return int(input())
def read_ints(): return list(map(int, input().split()))
def read_chars(): return list(input())
def read_pair(): return map(int, input().split())

# ---------- CONSTANTS ----------
MOD = 10**9 + 7
INF = float('inf')

# ---------- MATH HELPERS ----------
def gcd(a, b): return math.gcd(a, b)
def lcm(a, b): return a * b // math.gcd(a, b)
def power(a, b, mod=MOD): return pow(a, b, mod)
def modinv(a, mod=MOD): return pow(a, mod - 2, mod)

def nCr(n, r, mod=MOD):
    if r < 0 or r > n: return 0
    num = den = 1
    for i in range(r):
        num = (num * (n - i)) % mod
        den = (den * (i + 1)) % mod
    return num * modinv(den, mod) % mod

# Precompute factorials if needed (uncomment + adjust N)
# N = 2 * 10**5 + 5
# fact = [1] * N
# invfact = [1] * N
# for i in range(1, N):
#     fact[i] = fact[i-1] * i % MOD
# invfact[-1] = pow(fact[-1], MOD-2, MOD)
# for i in range(N-2, -1, -1):
#     invfact[i] = invfact[i+1] * (i+1) % MOD
# def nCr_fast(n, r):
#     if r < 0 or r > n: return 0
#     return fact[n] * invfact[r] % MOD * invfact[n-r] % MOD

# ---------- SORTING / SEARCH HELPERS ----------
def sort_by_second(arr): return sorted(arr, key=lambda x: x[1])
def sort_by_first(arr): return sorted(arr, key=lambda x: x[0])

def binary_search(arr, target):
    l, r = 0, len(arr) - 1
    while l <= r:
        m = (l + r) // 2
        if arr[m] == target: return m
        elif arr[m] < target: l = m + 1
        else: r = m - 1
    return -1

def lower_bound(arr, x):  # first index >= x
    return bisect_left(arr, x)

def upper_bound(arr, x):  # first index > x
    return bisect_right(arr, x)

# ---------- PREFIX / SUFFIX ----------
def prefix_sum(arr):
    ps = [0]
    for x in arr: ps.append(ps[-1] + x)
    return ps  # ps[i] = sum of arr[:i]

# ---------- GRID HELPERS ----------
# 4-directional and 8-directional movement
DIR4 = [(1, 0), (-1, 0), (0, 1), (0, -1)]
DIR8 = DIR4 + [(1, 1), (1, -1), (-1, 1), (-1, -1)]

def in_bounds(x, y, n, m):
    return 0 <= x < n and 0 <= y < m

# ---------- GRAPH HELPERS ----------
def build_graph(n, edges, directed=False, one_indexed=True):
    """
    n: number of nodes
    edges: list of (u, v)
    returns adjacency list
    """
    size = n + 1 if one_indexed else n
    g = [[] for _ in range(size)]
    for u, v in edges:
        g[u].append(v)
        if not directed:
            g[v].append(u)
    return g

def bfs(start, g):
    n = len(g)
    dist = [-1] * n
    q = deque([start])
    dist[start] = 0
    while q:
        u = q.popleft()
        for v in g[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist


def dfs(u, g, vis):
    vis[u] = True
    for v in g[u]:
        if not vis[v]:
            dfs(v, g, vis)

# ---------- DP / RECURSION MEMO ----------
def memoize(f):
    memo = {}
    def helper(*args):
        if args not in memo:
            memo[args] = f(*args)
        return memo[args]
    return helper

# ---------- OUTPUT HELPERS ----------
YES = "YES"
NO = "NO"
def yn(flag): print(YES if flag else NO)



# ---------- MAIN SOLVER ----------
def solve():
    n, m = read_pair()
    A = read_ints()
    D = DSU(n)
    
    M = set()
    for _ in range(m):
        u, v = read_pair()
        D.union(u - 1, v - 1)
        
    seen = {}
        
    for i in range(n):
        k = D.find(i)
        if k not in seen:
            M.add(D.extract(k))
            seen[k] = True
    
    ans = 1
    for s in M:
        a = sum(A[i] for i in s)
        ans *= (a ** len(s)) % 998244353
        
    print(ans % 998244353)

# ---------- DRIVER ----------
if __name__ == "__main__":
    t = 1  # set t = 1 for single test case problems
    for _ in range(t):
        solve()
0