For problem statement at 0-999/500-599/500-509/500/problemG.txt this is a correct solution, but verifier at 0-999/500-599/500-509/500/verifierG.go ends with ref failed on case 1: runtime error: exit status 1
# command-line-arguments
./500G.go:96:10: declared and not used: y
exit status 1 can you fix the verifier? ```go
package main
import (
"bufio"
"fmt"
"math/bits"
"os"
"sort"
)
var up [][]int
var depth []int
func buildLCA(n int, adj [][]int) {
up = make([][]int, n+1)
depth = make([]int, n+1)
for i := range up {
up[i] = make([]int, 20)
}
var dfs func(u, p, d int)
dfs = func(u, p, d int) {
up[u][0] = p
depth[u] = d
for i := 1; i < 20; i++ {
up[u][i] = up[up[u][i-1]][i-1]
}
for _, v := range adj[u] {
if v != p {
dfs(v, u, d+1)
}
}
}
dfs(1, 1, 0)
}
func lca(u, v int) int {
if depth[u] < depth[v] {
u, v = v, u
}
diff := depth[u] - depth[v]
for i := 0; i < 20; i++ {
if (diff & (1 << i)) != 0 {
u = up[u][i]
}
}
if u == v {
return u
}
for i := 19; i >= 0; i-- {
if up[u][i] != up[v][i] {
u = up[u][i]
v = up[v][i]
}
}
return up[u][0]
}
func dist(u, v int) int {
return depth[u] + depth[v] - 2*depth[lca(u, v)]
}
func exgcd(a, b int) (int, int, int) {
if b == 0 {
return a, 1, 0
}
g, x, y := exgcd(b, a%b)
return g, y, x - (a/b)*y
}
func gcd(a, b int) int {
for b != 0 {
a, b = b, a%b
}
return a
}
func crt(X, A, Y, B int) (int, bool) {
g, u, _ := exgcd(A, B)
if (Y-X)%g != 0 {
return 0, false
}
L := (A / g) * B
diff := Y - X
mult := diff / g
modBg := B / g
mult %= modBg
if mult < 0 {
mult += modBg
}
u %= modBg
if u < 0 {
u += modBg
}
term := (u * mult) % modBg
T := (X + A*term) % L
if T < 0 {
T += L
}
return T, true
}
func mulDiv(y, M, S, D int) int {
hi, lo := bits.Mul64(uint64(y), uint64(M))
lo, carry := bits.Add64(lo, uint64(D-1), 0)
hi, _ = bits.Add64(hi, 0, carry)
lo, borrow := bits.Sub64(lo, uint64(S), 0)
hi, _ = bits.Sub64(hi, 0, borrow)
q, _ := bits.Div64(hi, lo, uint64(D))
return int(q)
}
func min_x(S, D, M, K int) int {
if S <= K {
return 0
}
if D == 0 {
return -1
}
if K >= D {
return (M - S + D - 1) / D
}
S_prime := (D - (S % D)) % D
S_double_prime := (S_prime + (M % D)) % D
y_prime := min_x(S_double_prime, M%D, D, K)
if y_prime == -1 {
return -1
}
y := y_prime + 1
return mulDiv(y, M, S, D)
}
func solveType12(X, Y, A, B, g, L int) int {
if X%g != Y%g {
return -1
}
remA := X % A
remB := Y % B
T_base, ok := crt(remA, A, remB, B)
if !ok {
return -1
}
M := X
if Y > M {
M = Y
}
if T_base >= M {
return T_base
}
c := (M - T_base + L - 1) / L
return T_base + c*L
}
func solveType34(X, Y, K, A, B, g, L int) int {
S := X + Y + K
if S%2 != 0 {
return -1
}
t0 := (S / 2) % (g / 2)
remA := (t0 - X) % A
if remA < 0 {
remA += A
}
remB := (Y + K - t0) % B
if remB < 0 {
remB += B
}
I0, ok1 := crt(remA, A, remB, B)
remDA := (g / 2) % A
remDB := (-g / 2) % B
if remDB < 0 {
remDB += B
}
D, ok2 := crt(remDA, A, remDB, B)
if ok1 && ok2 {
M := X
if Y > M {
M = Y
}
k_min := 0
if t0 < M {
k_min = (M - t0 + (g / 2) - 1) / (g / 2)
}
I_start := (I0 + (k_min%L)*D%L) % L
k_ans := min_x(I_start, D, L, K)
if k_ans != -1 {
return t0 + (k_min+k_ans)*(g/2)
}
}
return -1
}
func main() {
scanner := bufio.NewScanner(os.Stdin)
scanner.Split(bufio.ScanWords)
buf := make([]byte, 1024*1024*8)
scanner.Buffer(buf, 1024*1024*8)
readInt := func() int {
scanner.Scan()
res := 0
for _, b := range scanner.Bytes() {
res = res*10 + int(b-'0')
}
return res
}
if !scanner.Scan() {
return
}
n := 0
for _, b := range scanner.Bytes() {
n = n*10 + int(b-'0')
}
adj := make([][]int, n+1)
for i := 0; i < n-1; i++ {
u, v := readInt(), readInt()
adj[u] = append(adj[u], v)
adj[v] = append(adj[v], u)
}
buildLCA(n, adj)
t := readInt()
for i := 0; i < t; i++ {
u := readInt()
v := readInt()
x := readInt()
y := readInt()
lca_uv := lca(u, v)
lca_xy := lca(x, y)
lcas := []int{lca(u, x), lca(u, y), lca(v, x), lca(v, y)}
sort.Slice(lcas, func(i, j int) bool {
return depth[lcas[i]] > depth[lcas[j]]
})
if depth[lcas[0]] < depth[lca_uv] || depth[lcas[0]] < depth[lca_xy] {
fmt.Println("-1")
continue
}
E1 := lcas[0]
E2 := lcas[1]
K := dist(E1, E2)
L1 := dist(u, v)
L2 := dist(x, y)
A := 2 * L1
B := 2 * L2
if dist(u, E1) > dist(u, E2) {
E1, E2 = E2, E1
}
U1 := dist(u, E1)
V1 := 2*L1 - dist(u, E2)
U2, V2 := 0, 0
if dist(x, E1) < dist(x, E2) || (K == 0 && dist(x, E1) <= dist(x, E2)) {
U2 = dist(x, E1)
V2 = 2*L2 - dist(x, E2)
} else {
U2 = 2*L2 - dist(x, E1)
V2 = dist(x, E2)
}
g := gcd(A, B)
L := (A / g) * B
ans := int64(-1)
updateAns := func(tVal int) {
if tVal != -1 {
if ans == -1 || int64(tVal) < ans {
ans = int64(tVal)
}
}
}
updateAns(solveType12(U1, U2, A, B, g, L))
updateAns(solveType12(V1, V2, A, B, g, L))
updateAns(solveType34(U1, V2, K, A, B, g, L))
updateAns(solveType34(V1, U2, K, A, B, g, L))
fmt.Println(ans)
}
}
```