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])
}
}