← Home
For problem statement at 0-999/900-999/960-969/960/problemF.txt this is a correct solution, but verifier at 0-999/900-999/960-969/960/verifierF.go ends with All tests passed can you fix the verifier? package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"sort"
)

type Edge struct {
	a, b, w int
}

func unique(a []int) []int {
	if len(a) == 0 {
		return a
	}
	sort.Ints(a)
	j := 1
	for i := 1; i < len(a); i++ {
		if a[i] != a[j-1] {
			a[j] = a[i]
			j++
		}
	}
	return a[:j]
}

func query(bit []int, idx int) int {
	res := 0
	for idx > 0 {
		if bit[idx] > res {
			res = bit[idx]
		}
		idx -= idx & -idx
	}
	return res
}

func update(bit []int, idx, val int) {
	for idx < len(bit) {
		if val > bit[idx] {
			bit[idx] = val
		}
		idx += idx & -idx
	}
}

func main() {
	data, _ := io.ReadAll(os.Stdin)
	p := 0
	nextInt := func() int {
		for p < len(data) && (data[p] < '0' || data[p] > '9') {
			p++
		}
		x := 0
		for p < len(data) && data[p] >= '0' && data[p] <= '9' {
			x = x*10 + int(data[p]-'0')
			p++
		}
		return x
	}

	n := nextInt()
	m := nextInt()

	edges := make([]Edge, m)
	weights := make([][]int, n+1)

	for i := 0; i < m; i++ {
		a := nextInt()
		b := nextInt()
		w := nextInt()
		edges[i] = Edge{a: a, b: b, w: w}
		weights[b] = append(weights[b], w)
	}

	bits := make([][]int, n+1)
	for v := 1; v <= n; v++ {
		weights[v] = unique(weights[v])
		bits[v] = make([]int, len(weights[v])+1)
	}

	ans := 0
	for i := 0; i < m; i++ {
		e := edges[i]
		pos := sort.SearchInts(weights[e.a], e.w)
		best := query(bits[e.a], pos)
		cur := best + 1

		posb := sort.SearchInts(weights[e.b], e.w) + 1
		update(bits[e.b], posb, cur)

		if cur > ans {
			ans = cur
		}
	}

	out := bufio.NewWriter(os.Stdout)
	fmt.Fprintln(out, ans)
	out.Flush()
}