結果

問題 No.2494 Sum within Components
ユーザー yassu0320
提出日時 2023-10-07 09:02:20
言語 Nim
(2.2.0)
結果
AC  
実行時間 93 ms / 2,000 ms
コード長 4,977 bytes
コンパイル時間 3,628 ms
コンパイル使用メモリ 74,036 KB
実行使用メモリ 15,568 KB
最終ジャッジ日時 2024-07-26 17:44:10
合計ジャッジ時間 5,046 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
/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
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0