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