← Home
For problem statement at 1000-1999/1800-1899/1810-1819/1819/problemD.txt this is a correct solution, but verifier at 1000-1999/1800-1899/1810-1819/1819/verifierD.go ends with case 10 failed
input:
1
2 2
1 2
2 1 2
expected:2
got:0

exit status 1 can you fix the verifier? package main

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

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1024*1024), 1024*1024*10)

	if !scanner.Scan() {
		return
	}
	t, _ := strconv.Atoi(scanner.Text())

	const INF int = 1e9
	next_seen := make([]int, 200005)
	for i := range next_seen {
		next_seen[i] = INF
	}

	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	for tc := 0; tc < t; tc++ {
		scanner.Scan()
		n, _ := strconv.Atoi(scanner.Text())
		scanner.Scan()
		m, _ := strconv.Atoi(scanner.Text())

		T := make([][]int, n+1)
		suffix_size := make([]int, n+2)

		for i := 1; i <= n; i++ {
			scanner.Scan()
			k, _ := strconv.Atoi(scanner.Text())
			T[i] = make([]int, k)
			for j := 0; j < k; j++ {
				scanner.Scan()
				T[i][j], _ = strconv.Atoi(scanner.Text())
			}
		}

		for i := n; i >= 1; i-- {
			suffix_size[i] = suffix_size[i+1] + len(T[i])
		}

		nxt_unknown := make([]int, n+2)
		curr_unk := INF
		for i := n; i >= 0; i-- {
			nxt_unknown[i] = curr_unk
			if i > 0 && len(T[i]) == 0 {
				curr_unk = i
			}
		}

		nxt_conflict := make([]int, n+2)
		min_R := INF
		for i := n; i >= 1; i-- {
			R_i := INF
			for _, e := range T[i] {
				if next_seen[e] < R_i {
					R_i = next_seen[e]
				}
				next_seen[e] = i
			}
			if R_i < min_R {
				min_R = R_i
			}
			nxt_conflict[i-1] = min_R
		}

		dp := make([]int, n+2)
		dp[n] = 0

		for i := n - 1; i >= 0; i-- {
			unk := nxt_unknown[i]
			conf := nxt_conflict[i]

			if unk == INF {
				if conf == INF {
					dp[i] = suffix_size[i+1]
				} else {
					dp[i] = dp[conf]
				}
			} else {
				if conf < unk {
					dp[i] = dp[conf]
				} else {
					if conf == INF {
						dp[i] = m
					} else {
						dp[i] = dp[unk]
					}
				}
			}
		}

		fmt.Fprintln(out, dp[0])

		for i := 1; i <= n; i++ {
			for _, e := range T[i] {
				next_seen[e] = INF
			}
		}
	}
}