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)
}