← Home
For problem statement at 1000-1999/1200-1299/1260-1269/1263/problemF.txt this is a correct solution, but verifier at 1000-1999/1200-1299/1260-1269/1263/verifierF.go ends with case 21 failed: expected 2 got 3
input:
1
3
1 1 
3 
3
1 1 
3 
exit status 1 can you fix the verifier? package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	in := bufio.NewReader(os.Stdin)

	var n int
	fmt.Fscan(in, &n)

	var a int
	fmt.Fscan(in, &a)

	p := make([]int, a-1)
	for i := 0; i < a-1; i++ {
		fmt.Fscan(in, &p[i])
	}

	x := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(in, &x[i])
	}

	var b int
	fmt.Fscan(in, &b)

	q := make([]int, b-1)
	for i := 0; i < b-1; i++ {
		fmt.Fscan(in, &q[i])
	}

	y := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(in, &y[i])
	}

	depth1 := make([]int, a+1)
	up1 := make([][12]int, a+1)
	adj1 := make([][]int, a+1)
	for i := 2; i <= a; i++ {
		p_i := p[i-2]
		adj1[p_i] = append(adj1[p_i], i)
	}

	var dfs1 func(u, p, d int)
	dfs1 = func(u, p, d int) {
		depth1[u] = d
		up1[u][0] = p
		for j := 1; j < 12; j++ {
			up1[u][j] = up1[up1[u][j-1]][j-1]
		}
		for _, v := range adj1[u] {
			if v != p {
				dfs1(v, u, d+1)
			}
		}
	}
	dfs1(1, 1, 0)

	lca1 := func(u, v int) int {
		if depth1[u] < depth1[v] {
			u, v = v, u
		}
		diff := depth1[u] - depth1[v]
		for j := 0; j < 12; j++ {
			if (diff & (1 << j)) != 0 {
				u = up1[u][j]
			}
		}
		if u == v {
			return u
		}
		for j := 11; j >= 0; j-- {
			if up1[u][j] != up1[v][j] {
				u = up1[u][j]
				v = up1[v][j]
			}
		}
		return up1[u][0]
	}

	depth2 := make([]int, b+1)
	up2 := make([][12]int, b+1)
	adj2 := make([][]int, b+1)
	for i := 2; i <= b; i++ {
		q_i := q[i-2]
		adj2[q_i] = append(adj2[q_i], i)
	}

	var dfs2 func(u, p, d int)
	dfs2 = func(u, p, d int) {
		depth2[u] = d
		up2[u][0] = p
		for j := 1; j < 12; j++ {
			up2[u][j] = up2[up2[u][j-1]][j-1]
		}
		for _, v := range adj2[u] {
			if v != p {
				dfs2(v, u, d+1)
			}
		}
	}
	dfs2(1, 1, 0)

	lca2 := func(u, v int) int {
		if depth2[u] < depth2[v] {
			u, v = v, u
		}
		diff := depth2[u] - depth2[v]
		for j := 0; j < 12; j++ {
			if (diff & (1 << j)) != 0 {
				u = up2[u][j]
			}
		}
		if u == v {
			return u
		}
		for j := 11; j >= 0; j-- {
			if up2[u][j] != up2[v][j] {
				u = up2[u][j]
				v = up2[v][j]
			}
		}
		return up2[u][0]
	}

	cost1 := func(u, v int) int {
		if u == 0 {
			return depth1[x[v-1]]
		}
		return depth1[x[v-1]] - depth1[lca1(x[u-1], x[v-1])]
	}

	cost2 := func(u, v int) int {
		if u == 0 {
			return depth2[y[v-1]]
		}
		return depth2[y[v-1]] - depth2[lca2(y[u-1], y[v-1])]
	}

	dp1 := make([]int, n)
	dp2 := make([]int, n)
	for i := range dp1 {
		dp1[i] = 1e9
		dp2[i] = 1e9
	}
	dp1[0] = cost1(0, 1)
	dp2[0] = cost2(0, 1)

	for k := 2; k <= n; k++ {
		new_dp1 := make([]int, n)
		new_dp2 := make([]int, n)
		for i := range new_dp1 {
			new_dp1[i] = 1e9
			new_dp2[i] = 1e9
		}

		for last := 0; last <= k-2; last++ {
			if dp1[last] != 1e9 {
				if val := dp1[last] + cost1(k-1, k); val < new_dp1[last] {
					new_dp1[last] = val
				}
			}
			if dp2[last] != 1e9 {
				if val := dp2[last] + cost2(k-1, k); val < new_dp2[last] {
					new_dp2[last] = val
				}
			}
		}

		for last1 := 0; last1 <= k-2; last1++ {
			if dp2[last1] != 1e9 {
				if val := dp2[last1] + cost1(last1, k); val < new_dp1[k-1] {
					new_dp1[k-1] = val
				}
			}
		}

		for last2 := 0; last2 <= k-2; last2++ {
			if dp1[last2] != 1e9 {
				if val := dp1[last2] + cost2(last2, k); val < new_dp2[k-1] {
					new_dp2[k-1] = val
				}
			}
		}

		dp1 = new_dp1
		dp2 = new_dp2
	}

	ans := int(1e9)
	for i := 0; i < n; i++ {
		if dp1[i] < ans {
			ans = dp1[i]
		}
		if dp2[i] < ans {
			ans = dp2[i]
		}
	}

	fmt.Println((a - 1) + (b - 1) - ans)
}