For problem statement at 2000-2999/2000-2099/2020-2029/2022/problemE2.txt this is a correct solution, but verifier at 2000-2999/2000-2099/2020-2029/2022/verifierE2.go ends with All 201 tests passed can you fix the verifier? package main
import (
"io"
"os"
"strconv"
)
const MOD = 1000000007
const MAXEXP = 6000000
type DSU struct {
p []int
sz []int
xr []int
}
func NewDSU(n int) *DSU {
p := make([]int, n)
sz := make([]int, n)
xr := make([]int, n)
for i := 0; i < n; i++ {
p[i] = i
sz[i] = 1
}
return &DSU{p: p, sz: sz, xr: xr}
}
func (d *DSU) Find(x int) (int, int) {
if d.p[x] == x {
return x, 0
}
r, v := d.Find(d.p[x])
d.xr[x] ^= v
d.p[x] = r
return d.p[x], d.xr[x]
}
func (d *DSU) Union(x, y, w int) (bool, bool) {
rx, vx := d.Find(x)
ry, vy := d.Find(y)
if rx == ry {
return (vx ^ vy) == w, false
}
ww := vx ^ vy ^ w
if d.sz[rx] < d.sz[ry] {
rx, ry = ry, rx
}
d.p[ry] = rx
d.xr[ry] = ww
d.sz[rx] += d.sz[ry]
return true, true
}
func main() {
pow2 := make([]int, MAXEXP+1)
pow2[0] = 1
for i := 1; i <= MAXEXP; i++ {
pow2[i] = (pow2[i-1] * 2) % MOD
}
data, _ := io.ReadAll(os.Stdin)
idx := 0
nextInt := func() int {
for idx < len(data) && (data[idx] < '0' || data[idx] > '9') {
idx++
}
val := 0
for idx < len(data) && data[idx] >= '0' && data[idx] <= '9' {
val = val*10 + int(data[idx]-'0')
idx++
}
return val
}
t := nextInt()
out := make([]byte, 0, 1<<20)
for ; t > 0; t-- {
n := nextInt()
m := nextInt()
k := nextInt()
q := nextInt()
dsu := NewDSU(n + m)
cc := n + m
bad := false
for i := 0; i < k; i++ {
r := nextInt()
c := nextInt()
v := nextInt()
if !bad {
ok, merged := dsu.Union(r-1, n+c-1, v)
if !ok {
bad = true
} else if merged {
cc--
}
}
}
if bad {
out = strconv.AppendInt(out, 0, 10)
} else {
out = strconv.AppendInt(out, int64(pow2[30*(cc-1)]), 10)
}
out = append(out, '\n')
for i := 0; i < q; i++ {
r := nextInt()
c := nextInt()
v := nextInt()
if !bad {
ok, merged := dsu.Union(r-1, n+c-1, v)
if !ok {
bad = true
} else if merged {
cc--
}
}
if bad {
out = strconv.AppendInt(out, 0, 10)
} else {
out = strconv.AppendInt(out, int64(pow2[30*(cc-1)]), 10)
}
out = append(out, '\n')
}
}
os.Stdout.Write(out)
}