← Home
For problem statement at 1000-1999/1600-1699/1620-1629/1624/problemG.txt this is a correct solution, but verifier at 1000-1999/1600-1699/1620-1629/1624/verifierG.go ends with case 1 failed: expected 2147483647 got 1073741823
exit status 1 can you fix the verifier? package main

import (
	"bytes"
	"io"
	"os"
	"strconv"
)

type FastScanner struct {
	data []byte
	idx  int
	n    int
}

func NewFastScanner() *FastScanner {
	data, _ := io.ReadAll(os.Stdin)
	return &FastScanner{data: data, n: len(data)}
}

func (fs *FastScanner) NextInt() int {
	for fs.idx < fs.n && (fs.data[fs.idx] < '0' || fs.data[fs.idx] > '9') && fs.data[fs.idx] != '-' {
		fs.idx++
	}
	sign := 1
	if fs.idx < fs.n && fs.data[fs.idx] == '-' {
		sign = -1
		fs.idx++
	}
	val := 0
	for fs.idx < fs.n && fs.data[fs.idx] >= '0' && fs.data[fs.idx] <= '9' {
		val = val*10 + int(fs.data[fs.idx]-'0')
		fs.idx++
	}
	return val * sign
}

type Edge struct {
	u, v int
	w    int
}

type DSU struct {
	p  []int
	sz []int
}

func NewDSU(n int) *DSU {
	return &DSU{
		p:  make([]int, n+1),
		sz: make([]int, n+1),
	}
}

func (d *DSU) Init(n int) {
	if len(d.p) < n+1 {
		d.p = make([]int, n+1)
		d.sz = make([]int, n+1)
	}
	for i := 1; i <= n; i++ {
		d.p[i] = i
		d.sz[i] = 1
	}
}

func (d *DSU) Find(x int) int {
	root := x
	for d.p[root] != root {
		root = d.p[root]
	}
	for x != root {
		px := d.p[x]
		d.p[x] = root
		x = px
	}
	return root
}

func (d *DSU) Union(a, b int) bool {
	ra := d.Find(a)
	rb := d.Find(b)
	if ra == rb {
		return false
	}
	if d.sz[ra] < d.sz[rb] {
		ra, rb = rb, ra
	}
	d.p[rb] = ra
	d.sz[ra] += d.sz[rb]
	return true
}

func main() {
	fs := NewFastScanner()
	t := fs.NextInt()
	var out bytes.Buffer

	for ; t > 0; t-- {
		n := fs.NextInt()
		m := fs.NextInt()
		edges := make([]Edge, m)
		for i := 0; i < m; i++ {
			u := fs.NextInt()
			v := fs.NextInt()
			w := fs.NextInt()
			edges[i] = Edge{u: u, v: v, w: w}
		}

		dsu := NewDSU(n)
		can := func(mask int) bool {
			dsu.Init(n)
			comp := n
			for _, e := range edges {
				if e.w&mask == 0 {
					if dsu.Union(e.u, e.v) {
						comp--
						if comp == 1 {
							return true
						}
					}
				}
			}
			return comp == 1
		}

		forbidden := 0
		ans := 0
		for b := 29; b >= 0; b-- {
			mask := forbidden | (1 << b)
			if can(mask) {
				forbidden = mask
			} else {
				ans |= 1 << b
			}
		}

		out.WriteString(strconv.Itoa(ans))
		out.WriteByte('\n')
	}

	os.Stdout.Write(out.Bytes())
}