← Home
For problem statement at 0-999/500-599/580-589/587/problemC.txt this is a correct solution, but verifier at 0-999/500-599/580-589/587/verifierC.go ends with All tests passed can you fix the verifier? package main

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

type Top10 struct {
	a [10]int
	n int
}

func merge(x, y Top10) Top10 {
	var res Top10
	i, j := 0, 0
	for i < x.n && j < y.n && res.n < 10 {
		if x.a[i] < y.a[j] {
			res.a[res.n] = x.a[i]
			res.n++
			i++
		} else if x.a[i] > y.a[j] {
			res.a[res.n] = y.a[j]
			res.n++
			j++
		} else {
			res.a[res.n] = x.a[i]
			res.n++
			i++
			j++
		}
	}
	for i < x.n && res.n < 10 {
		res.a[res.n] = x.a[i]
		res.n++
		i++
	}
	for j < y.n && res.n < 10 {
		res.a[res.n] = y.a[j]
		res.n++
		j++
	}
	return res
}

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

func main() {
	reader := bufio.NewReaderSize(os.Stdin, 65536)
	writer := bufio.NewWriterSize(os.Stdout, 65536)
	defer writer.Flush()

	n := readInt(reader)
	m := readInt(reader)
	q := readInt(reader)

	if n == 0 {
		return
	}

	adj := make([][]int, n+1)
	for i := 0; i < n-1; i++ {
		u := readInt(reader)
		v := readInt(reader)
		adj[u] = append(adj[u], v)
		adj[v] = append(adj[v], u)
	}

	const LOG = 18
	up := make([][LOG]int, n+1)
	data := make([][LOG]Top10, n+1)
	depth := make([]int, n+1)

	for i := 1; i <= m; i++ {
		c := readInt(reader)
		if data[c][0].n < 10 {
			data[c][0].a[data[c][0].n] = i
			data[c][0].n++
		}
	}

	var dfs func(v, p, d int)
	dfs = func(v, p, d int) {
		up[v][0] = p
		depth[v] = d
		for _, to := range adj[v] {
			if to != p {
				dfs(to, v, d+1)
			}
		}
	}
	dfs(1, 1, 0)

	for j := 1; j < LOG; j++ {
		for i := 1; i <= n; i++ {
			up[i][j] = up[up[i][j-1]][j-1]
			data[i][j] = merge(data[i][j-1], data[up[i][j-1]][j-1])
		}
	}

	for i := 0; i < q; i++ {
		u := readInt(reader)
		v := readInt(reader)
		a := readInt(reader)

		var ans Top10

		if depth[u] < depth[v] {
			u, v = v, u
		}
		diff := depth[u] - depth[v]
		for j := 0; j < LOG; j++ {
			if (diff & (1 << j)) != 0 {
				ans = merge(ans, data[u][j])
				u = up[u][j]
			}
		}

		if u == v {
			ans = merge(ans, data[u][0])
		} else {
			for j := LOG - 1; j >= 0; j-- {
				if up[u][j] != up[v][j] {
					ans = merge(ans, data[u][j])
					ans = merge(ans, data[v][j])
					u = up[u][j]
					v = up[v][j]
				}
			}
			ans = merge(ans, data[u][0])
			ans = merge(ans, data[v][0])
			ans = merge(ans, data[up[u][0]][0])
		}

		k := ans.n
		if k > a {
			k = a
		}
		fmt.Fprint(writer, k)
		for j := 0; j < k; j++ {
			fmt.Fprint(writer, " ", ans.a[j])
		}
		fmt.Fprintln(writer)
	}
}