← Home
For problem statement at 0-999/500-599/500-509/506/problemD.txt this is a correct solution, but verifier at 0-999/500-599/500-509/506/verifierD.go ends with failed to build reference: REFERENCE_SOURCE_PATH not set

exit status 1 can you fix the verifier? package main

import (
	"bufio"
	"os"
	"strconv"
)

func readInt(in *bufio.Reader) int {
	var n int
	var c byte
	var err error
	for {
		c, err = in.ReadByte()
		if err != nil {
			return 0
		}
		if c >= '0' && c <= '9' {
			n = int(c - '0')
			break
		}
	}
	for {
		c, err = in.ReadByte()
		if err != nil {
			break
		}
		if c >= '0' && c <= '9' {
			n = n*10 + int(c-'0')
		} else {
			break
		}
	}
	return n
}

func main() {
	in := bufio.NewReaderSize(os.Stdin, 1<<20)
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	n := readInt(in)
	m := readInt(in)
	if n == 0 {
		return
	}

	type Edge struct {
		u, v int
	}
	edgesByColor := make([][]Edge, m+1)
	for i := 0; i < m; i++ {
		u := readInt(in)
		v := readInt(in)
		c := readInt(in)
		edgesByColor[c] = append(edgesByColor[c], Edge{u, v})
	}

	parent := make([]int, n+1)
	for i := 1; i <= n; i++ {
		parent[i] = i
	}
	compID := make([]int, n+1)
	visited := make([]bool, n+1)
	var nodes []int

	find := func(i int) int {
		root := i
		for root != parent[root] {
			root = parent[root]
		}
		curr := i
		for curr != root {
			nxt := parent[curr]
			parent[curr] = root
			curr = nxt
		}
		return root
	}

	globalID := 0
	comps := make([][]int, n+1)

	for c := 1; c <= m; c++ {
		if len(edgesByColor[c]) == 0 {
			continue
		}
		nodes = nodes[:0]
		for _, e := range edgesByColor[c] {
			if !visited[e.u] {
				visited[e.u] = true
				nodes = append(nodes, e.u)
			}
			if !visited[e.v] {
				visited[e.v] = true
				nodes = append(nodes, e.v)
			}
		}

		for _, e := range edgesByColor[c] {
			ru := find(e.u)
			rv := find(e.v)
			if ru != rv {
				parent[ru] = rv
			}
		}

		for _, u := range nodes {
			root := find(u)
			if compID[root] == 0 {
				globalID++
				compID[root] = globalID
			}
			comps[u] = append(comps[u], compID[root])
		}

		for _, u := range nodes {
			parent[u] = u
			compID[u] = 0
			visited[u] = false
		}
	}

	q := readInt(in)
	memo := make(map[int64]int)

	for i := 0; i < q; i++ {
		u := readInt(in)
		v := readInt(in)
		if u > v {
			u, v = v, u
		}
		key := (int64(u) << 32) | int64(v)
		if ans, exists := memo[key]; exists {
			out.WriteString(strconv.Itoa(ans) + "\n")
			continue
		}

		c1, c2 := comps[u], comps[v]
		if len(c1) > len(c2) {
			c1, c2 = c2, c1
		}

		ans := 0
		if len(c1)*20 > len(c2) {
			i_idx, j_idx := 0, 0
			for i_idx < len(c1) && j_idx < len(c2) {
				if c1[i_idx] == c2[j_idx] {
					ans++
					i_idx++
					j_idx++
				} else if c1[i_idx] < c2[j_idx] {
					i_idx++
				} else {
					j_idx++
				}
			}
		} else {
			for _, id := range c1 {
				l, r := 0, len(c2)-1
				for l <= r {
					mid := (l + r) / 2
					if c2[mid] == id {
						ans++
						break
					} else if c2[mid] < id {
						l = mid + 1
					} else {
						r = mid - 1
					}
				}
			}
		}
		memo[key] = ans
		out.WriteString(strconv.Itoa(ans) + "\n")
	}
}