← Home
For problem statement at 1000-1999/1400-1499/1400-1409/1408/problemE.txt this is a correct solution, but verifier at 1000-1999/1400-1499/1400-1409/1408/verifierE.go ends with All tests passed can you fix the verifier? package main

import (
	"fmt"
	"io"
	"os"
	"sort"
)

type Edge struct {
	u, v int
	w    int64
}

type EdgeList []Edge

func (a EdgeList) Len() int           { return len(a) }
func (a EdgeList) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a EdgeList) Less(i, j int) bool { return a[i].w > a[j].w }

func main() {
	buf, _ := io.ReadAll(os.Stdin)
	pos := 0
	next := func() int {
		for pos < len(buf) && buf[pos] <= ' ' {
			pos++
		}
		if pos >= len(buf) {
			return 0
		}
		res := 0
		for pos < len(buf) && buf[pos] > ' ' {
			res = res*10 + int(buf[pos]-'0')
			pos++
		}
		return res
	}

	m := next()
	n := next()
	if m == 0 && n == 0 {
		return
	}

	a := make([]int64, m+1)
	for i := 1; i <= m; i++ {
		a[i] = int64(next())
	}
	b := make([]int64, n+1)
	for i := 1; i <= n; i++ {
		b[i] = int64(next())
	}

	var edges []Edge
	var totalCost int64

	for i := 1; i <= m; i++ {
		s := next()
		for j := 0; j < s; j++ {
			v := next()
			w := a[i] + b[v]
			edges = append(edges, Edge{i, m + v, w})
			totalCost += w
		}
	}

	sort.Sort(EdgeList(edges))

	parent := make([]int, m+n+1)
	for i := 1; i <= m+n; i++ {
		parent[i] = i
	}

	var find func(int) int
	find = func(x int) int {
		if parent[x] != x {
			parent[x] = find(parent[x])
		}
		return parent[x]
	}

	for _, e := range edges {
		pu := find(e.u)
		pv := find(e.v)
		if pu != pv {
			parent[pu] = pv
			totalCost -= e.w
		}
	}

	fmt.Println(totalCost)
}