← Home
For problem statement at 1000-1999/1700-1799/1790-1799/1795/problemG.txt this is a correct solution, but verifier at 1000-1999/1700-1799/1790-1799/1795/verifierG.go ends with case 1 failed: expected 0 got 2
input:
1
3 1
0 1 0
2 3

exit status 1 can you fix the verifier? package main

import (
	"io"
	"math/bits"
	"os"
)

const B = 2048
const words = B / 64

var bs [100005][words]uint64
var buffer []byte
var bufIdx int

func readInt() int {
	for bufIdx < len(buffer) && (buffer[bufIdx] < '0' || buffer[bufIdx] > '9') {
		bufIdx++
	}
	if bufIdx >= len(buffer) {
		return 0
	}
	res := 0
	for bufIdx < len(buffer) && buffer[bufIdx] >= '0' && buffer[bufIdx] <= '9' {
		res = res*10 + int(buffer[bufIdx]-'0')
		bufIdx++
	}
	return res
}

var out []byte

func writeInt(n int64) {
	if n == 0 {
		out = append(out, '0', '\n')
		return
	}
	var buf [20]byte
	i := 19
	for n > 0 {
		buf[i] = byte(n%10) + '0'
		n /= 10
		i--
	}
	out = append(out, buf[i+1:]...)
	out = append(out, '\n')
}

func main() {
	input, _ := io.ReadAll(os.Stdin)
	buffer = input
	bufIdx = 0

	t := readInt()
	if t == 0 {
		return
	}

	adj := make([][]int, 100005)
	dag := make([][]int, 100005)
	for i := range adj {
		adj[i] = make([]int, 0)
		dag[i] = make([]int, 0)
	}

	a := make([]int, 100005)
	deg := make([]int, 100005)
	req := make([]int, 100005)
	popped := make([]bool, 100005)
	topo := make([]int, 0, 100005)
	q := make([]int, 0, 100005)

	for tc := 0; tc < t; tc++ {
		n := readInt()
		m := readInt()

		for i := 1; i <= n; i++ {
			a[i] = readInt()
			deg[i] = 0
			adj[i] = adj[i][:0]
			dag[i] = dag[i][:0]
			popped[i] = false
		}

		for i := 0; i < m; i++ {
			u := readInt()
			v := readInt()
			adj[u] = append(adj[u], v)
			adj[v] = append(adj[v], u)
			deg[u]++
			deg[v]++
		}

		q = q[:0]
		for i := 1; i <= n; i++ {
			req[i] = deg[i] - a[i]
			if req[i] == 0 {
				q = append(q, i)
			}
		}

		topo = topo[:0]
		for len(q) > 0 {
			u := q[0]
			q = q[1:]
			popped[u] = true
			topo = append(topo, u)
			for _, v := range adj[u] {
				if !popped[v] {
					dag[u] = append(dag[u], v)
					req[v]--
					if req[v] == 0 {
						q = append(q, v)
					}
				}
			}
		}

		var totalComparable int64 = 0

		for L := 1; L <= n; L += B {
			R := L + B - 1
			if R > n {
				R = n
			}

			for i := 1; i <= n; i++ {
				bs[i] = [words]uint64{}
			}

			for i := n - 1; i >= 0; i-- {
				u := topo[i]
				for _, v := range dag[u] {
					if v >= L && v <= R {
						bs[u][(v-L)>>6] |= 1 << ((v - L) & 63)
					}
					for w := 0; w < words; w++ {
						bs[u][w] |= bs[v][w]
					}
				}
				for w := 0; w < words; w++ {
					totalComparable += int64(bits.OnesCount64(bs[u][w]))
				}
			}
		}

		totalPairs := int64(n) * int64(n-1) / 2
		nicePairs := totalPairs - totalComparable
		writeInt(nicePairs)
	}
	os.Stdout.Write(out)
}