結果

問題 No.2494 Sum within Components
ユーザー yassu0320yassu0320
提出日時 2023-10-07 09:02:20
言語 Nim
(2.0.2)
結果
AC  
実行時間 134 ms / 2,000 ms
コード長 4,977 bytes
コンパイル時間 3,777 ms
コンパイル使用メモリ 71,504 KB
実行使用メモリ 37,220 KB
最終ジャッジ日時 2023-10-07 09:02:25
合計ジャッジ時間 5,634 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 7 ms
4,376 KB
testcase_10 AC 11 ms
6,104 KB
testcase_11 AC 5 ms
4,704 KB
testcase_12 AC 13 ms
5,760 KB
testcase_13 AC 9 ms
5,312 KB
testcase_14 AC 92 ms
25,124 KB
testcase_15 AC 85 ms
17,564 KB
testcase_16 AC 66 ms
22,736 KB
testcase_17 AC 82 ms
37,220 KB
testcase_18 AC 90 ms
36,916 KB
testcase_19 AC 134 ms
35,516 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
/home/judge/data/code/Main.nim(1, 8) Warning: imported and not used: 'algorithm' [UnusedImport]
/home/judge/data/code/Main.nim(6, 11) Warning: imported and not used: 'math' [UnusedImport]
/home/judge/data/code/Main.nim(8, 8) Warning: imported and not used: 'strformat' [UnusedImport]
/home/judge/data/code/Main.nim(9, 8) Warning: imported and not used: 'strutils' [UnusedImport]

ソースコード

diff # 

import algorithm
import options
import sequtils
import sets
import std/heapqueue
import std/math
import std/tables
import strformat
import strutils

const letter: string = "abcdefghijklmnopqrstuvwxyz"
const Letter: string = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
const MAX_INT: int = high(int)
const MIN_INT: int = low(int)

proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc getchar(): char {.header: "<stdio.h>", varargs.}
proc nextInt(): int = scanf("%lld", addr result)
proc nextInts(n: int): seq[int] =
    var res = newSeq[int](n)
    for i in 0..<n:
        res[i] = nextInt()
    return res

proc nextInt64(): int64 = scanf("%lld", addr result)
proc nextUInt64(): uint64 = scanf("%lld", addr result)
proc nextFloat(): float = scanf("%lf", addr result)
proc nextString(): string =
    var get = false
    result = ""
    while true:
        var c = getchar()
        if int(c) > int(' '):
            get = true
            result.add(c)
        else:
            if get: break
            get = false

func toInt(b: bool): int =
    if b:
        return 1
    else:
        return 0

func `+`(a: int, b: bool): int = a + (b.toInt)
func `+`(a: bool, b: int): int = (a.toInt) + b
func `-`(a: int, b: bool): int = a - (b.toInt)
func `-`(a: bool, b: int): int = (a.toInt) - b
func `*`(a: int, b: bool): int = a * (b.toInt)
func `*`(a: bool, b: int): int = (a.toInt) * b

proc `|=`(a: var bool, b: bool) =
    a = a or b
func `|`(c1, c2: int): int = c1 or c2

proc `&=`(a: var bool, b: bool) =
    a = a and b
func `&`(c1, c2: int): int = c1 and c2

func `//`(a, b: int): int = a div b

proc `//=`(a: var int, b: int) =
    a = a div b

func `%`(a: int, b: Positive): int =
    result = a mod b
    if result < 0:
        result += b

proc `%=`(a: var int, b: int) =
    a = a mod b

func `<<`(a: int, s: int): int = a shl s
func `>>`(a: int, s: int): int = a shr s
proc `>>=`(a: var int, b: int) =
    a = a shr b

# Z/mo Z荳翫・a縺ｮ騾・・
func inv(a, mo: int): int =
    var r = (mo, a)
    var x = (0, 1)
    while r[1] != 0:
        x = (x[1], (x[0] - (r[0] div r[1]) * x[1]) % mo)
        r = (r[1], r[0] % r[1])

    if r[0] == 1:
        return x[0]
    else:
        return -1

func bitLength(n: Natural): int =
    result = 0
    var num = abs(n)
    while num > 0:
        result += 1
        num = num shr 1

proc chmax[T](a: var T, vars: varargs[T]): bool {.discardable.} =
    let target = max(vars)
    if a < target:
        a = target
        return true
    else:
        return false

proc chmin[T](a: var T, vars: varargs[T]): bool {.discardable.} =
    let target = min(vars)
    if a > target:
        a = target
        return true
    else:
        return false

template present(a: typed): bool = a.len != 0
template empty(a: typed): bool = a.len == 0

template rep(idx: untyped, n: SomeOrdinal, act: untyped): untyped =
    for idx in 0 ..< n:
        act

template loop(body: untyped): untyped =
    while true:
        body

func Yn(cond: bool, yes: string = "Yes", no: string = "No"): string =
    if cond:
        yes
    else:
        no

func `<`[T](u, v: openArray[T]): bool =
    assert u.len == v.len
    for j in 0..<u.len:
        if u[j] != v[j]:
            return u[j]-v[j] < 0

    return true

# start coding
# DSU {{{
const ATCODER_DSU_HPP* = 1

import std/sequtils

type
    DSU* = ref object
        n: int
        par_or_siz: seq[int]

proc initDSU*(n: int): DSU {.inline.} =
    return DSU(n: n, par_or_siz: newSeqWith(n, -1))

proc leader*(self: DSU; a: int): int {.inline.} =
    ## Path compression
    if self.par_or_siz[a] < 0: return a
    self.par_or_siz[a] = self.leader(self.par_or_siz[a])
    return self.par_or_siz[a]

proc same*(self: DSU; a, b: int): bool {.inline.} =
    self.leader(a) == self.leader(b)

proc size*(self: DSU; a: int): int {.inline.} =
    - self.par_or_siz[self.leader(a)]

proc merge*(self: DSU; a, b: int): int {.inline, discardable.} =

    var
        x = self.leader(a)
        y = self.leader(b)


    if x == y: return x
    if self.par_or_siz[x] > self.par_or_siz[y]: swap(x, y)
    self.par_or_siz[x] += self.par_or_siz[y]
    self.par_or_siz[y] = x
    return x

proc groups*(self: DSU): seq[seq[int]] {.inline.} =
    var
        leaderBuf = newSeq[int](self.n)
        groupsize = newSeq[int](self.n)
    for i in 0 ..< self.n:
        leaderBuf[i] = self.leader(i)
        groupsize[leaderBuf[i]].inc
    result = (0 ..< self.n).mapIt(newSeqOfCap[int](groupsize[it]))
    for i, ldr in leaderBuf:
        result[ldr].add i
    result.keepItIf(it.len > 0)
# }}}

let
    N = nextInt()
    M = nextInt()

let A = nextInts(N)
var dsu = initDSU(N)
for _ in 0..<M:
    let
        u = nextInt()-1
        v = nextInt()-1
    dsu.merge(u, v)

var res = 1
for gr in dsu.groups():
    var s = 0
    for u in gr:
        s += A[u]
        s %= 998244353
    var v = 1
    for i in 0..<gr.len:
        v *= s
        v %= 998244353
    res *= v
    res %= 998244353

echo res
0