← Home
For problem statement at 0-999/800-899/820-829/827/problemD.txt this is a correct solution, but verifier at 0-999/800-899/820-829/827/verifierD.go ends with  can you fix the verifier? package main

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

var buffer []byte = make([]byte, 1024*1024)
var index int
var bytesRead int

func readByte() byte {
	if index == bytesRead {
		bytesRead, _ = os.Stdin.Read(buffer)
		if bytesRead == 0 {
			return 0
		}
		index = 0
	}
	b := buffer[index]
	index++
	return b
}

func readInt() int {
	b := readByte()
	for b <= ' ' {
		if b == 0 {
			return 0
		}
		b = readByte()
	}
	res := 0
	for b > ' ' {
		res = res*10 + int(b-'0')
		b = readByte()
	}
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

type Edge struct {
	u, v, w, id int
}

type Next struct {
	v, w, id int
}

const MAXN = 200005
const LOG = 20

var (
	up          [MAXN][LOG]int
	maxW        [MAXN][LOG]int
	depth       [MAXN]int
	parent      [MAXN]int
	edgeIdAbove [MAXN]int
	dsuParent   [MAXN]int
	ans         []int
	adj         [][]Next
)

func dfs(u, p, pEdgeId, pWeight, d int) {
	up[u][0] = p
	maxW[u][0] = pWeight
	depth[u] = d
	parent[u] = p
	edgeIdAbove[u] = pEdgeId

	for i := 1; i < LOG; i++ {
		if up[u][i-1] != 0 {
			up[u][i] = up[up[u][i-1]][i-1]
			maxW[u][i] = max(maxW[u][i-1], maxW[up[u][i-1]][i-1])
		} else {
			up[u][i] = 0
			maxW[u][i] = maxW[u][i-1]
		}
	}

	for _, edge := range adj[u] {
		if edge.v != p {
			dfs(edge.v, u, edge.id, edge.w, d+1)
		}
	}
}

func queryMaxAndLCA(u, v int) (int, int) {
	res := 0
	if depth[u] < depth[v] {
		u, v = v, u
	}
	diff := depth[u] - depth[v]
	for i := 0; i < LOG; i++ {
		if (diff & (1 << i)) != 0 {
			res = max(res, maxW[u][i])
			u = up[u][i]
		}
	}
	if u == v {
		return res, u
	}
	for i := LOG - 1; i >= 0; i-- {
		if up[u][i] != up[v][i] {
			res = max(res, maxW[u][i])
			res = max(res, maxW[v][i])
			u = up[u][i]
			v = up[v][i]
		}
	}
	res = max(res, maxW[u][0])
	res = max(res, maxW[v][0])
	return res, up[u][0]
}

func findTree(i int) int {
	if dsuParent[i] == i {
		return i
	}
	dsuParent[i] = findTree(dsuParent[i])
	return dsuParent[i]
}

func main() {
	n := readInt()
	if n == 0 {
		return
	}
	m := readInt()

	edges := make([]Edge, m)
	for i := 0; i < m; i++ {
		edges[i] = Edge{
			u:  readInt(),
			v:  readInt(),
			w:  readInt(),
			id: i,
		}
	}

	sortedEdges := make([]Edge, m)
	copy(sortedEdges, edges)
	sort.Slice(sortedEdges, func(i, j int) bool {
		return sortedEdges[i].w < sortedEdges[j].w
	})

	parentKruskal := make([]int, n+1)
	for i := 1; i <= n; i++ {
		parentKruskal[i] = i
	}
	var findKruskal func(int) int
	findKruskal = func(i int) int {
		if parentKruskal[i] == i {
			return i
		}
		parentKruskal[i] = findKruskal(parentKruskal[i])
		return parentKruskal[i]
	}

	inMST := make([]bool, m)
	adj = make([][]Next, n+1)
	for i := 1; i <= n; i++ {
		adj[i] = make([]Next, 0, 2)
	}

	for _, e := range sortedEdges {
		u, v := e.u, e.v
		rootU := findKruskal(u)
		rootV := findKruskal(v)
		if rootU != rootV {
			parentKruskal[rootU] = rootV
			inMST[e.id] = true
			adj[u] = append(adj[u], Next{v, e.w, e.id})
			adj[v] = append(adj[v], Next{u, e.w, e.id})
		}
	}

	ans = make([]int, m)
	for i := 0; i < m; i++ {
		ans[i] = -1
	}

	dfs(1, 0, -1, 0, 1)

	for i := 1; i <= n; i++ {
		dsuParent[i] = i
	}

	for _, e := range sortedEdges {
		if !inMST[e.id] {
			u, v, w := e.u, e.v, e.w
			maxVal, lcaNode := queryMaxAndLCA(u, v)
			ans[e.id] = maxVal - 1

			curr := findTree(u)
			for depth[curr] > depth[lcaNode] {
				ans[edgeIdAbove[curr]] = w - 1
				dsuParent[curr] = findTree(parent[curr])
				curr = findTree(curr)
			}

			curr = findTree(v)
			for depth[curr] > depth[lcaNode] {
				ans[edgeIdAbove[curr]] = w - 1
				dsuParent[curr] = findTree(parent[curr])
				curr = findTree(curr)
			}
		}
	}

	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()
	for i := 0; i < m; i++ {
		fmt.Fprintln(out, ans[i])
	}
}