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