For problem statement at 0-999/200-299/240-249/240/problemE.txt this is a correct solution, but verifier at 0-999/200-299/240-249/240/verifierE.go ends with test 37 failed: expected 3 repairs but reported 4
input:
6 17
6 3 1
2 5 0
5 6 0
3 4 1
5 2 1
6 4 1
2 3 1
4 6 1
1 6 1
6 5 1
1 5 1
2 4 0
6 1 1
1 4 1
2 6 1
3 5 0
2 1 1
output:
4
5 1 11 8
expected minimal repairs: 3
exit status 1 can you fix the verifier? package main
import (
"bufio"
"fmt"
"os"
"strconv"
)
type Edge struct {
id, u, v, w int
}
type Node struct {
id, u, v, w int
lazy int
left, right *Node
}
func apply(n *Node, lazy int) {
if n != nil {
n.w += lazy
n.lazy += lazy
}
}
func push(n *Node) {
if n != nil && n.lazy != 0 {
apply(n.left, n.lazy)
apply(n.right, n.lazy)
n.lazy = 0
}
}
func merge(a, b *Node) *Node {
if a == nil {
return b
}
if b == nil {
return a
}
push(a)
push(b)
if a.w > b.w {
a, b = b, a
}
a.right = merge(a.right, b)
a.left, a.right = a.right, a.left
return a
}
func pop(n *Node) *Node {
push(n)
res := merge(n.left, n.right)
n.left = nil
n.right = nil
return res
}
func main() {
scanner := bufio.NewScanner(os.Stdin)
scanner.Split(bufio.ScanWords)
buf := make([]byte, 1024*1024)
scanner.Buffer(buf, 1024*1024*10)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
scanInt := func() int {
scanner.Scan()
x, _ := strconv.Atoi(scanner.Text())
return x
}
if !scanner.Scan() {
return
}
n, _ := strconv.Atoi(scanner.Text())
m := scanInt()
edges := make([]Edge, m+1)
adj := make([][]Edge, n+1)
for i := 1; i <= m; i++ {
u := scanInt()
v := scanInt()
w := scanInt()
edges[i] = Edge{i, u, v, w}
adj[u] = append(adj[u], edges[i])
}
reached := make([]bool, n+1)
q := []int{1}
reached[1] = true
for len(q) > 0 {
u := q[0]
q = q[1:]
for _, e := range adj[u] {
if !reached[e.v] {
reached[e.v] = true
q = append(q, e.v)
}
}
}
for i := 1; i <= n; i++ {
if !reached[i] {
fmt.Fprintln(out, "-1")
return
}
}
maxNodes := 2*n + 1
heaps := make([]*Node, maxNodes)
for i := 1; i <= m; i++ {
e := edges[i]
if e.v == 1 {
continue
}
nNode := &Node{id: e.id, u: e.u, v: e.v, w: e.w}
heaps[e.v] = merge(heaps[e.v], nNode)
}
parent := make([]int, maxNodes)
for i := 1; i < maxNodes; i++ {
parent[i] = i
}
find := func(i int) int {
root := i
for root != parent[root] {
root = parent[root]
}
curr := i
for curr != root {
nxt := parent[curr]
parent[curr] = root
curr = nxt
}
return root
}
visited := make([]int, maxNodes)
visited[1] = 2
enter := make([]*Node, maxNodes)
inEdge := make([]*Node, n+1)
compId := n
for i := 2; i <= n; i++ {
if visited[i] != 0 {
continue
}
curr := i
path := []int{curr}
visited[curr] = 1
for {
var minEdge *Node
for heaps[curr] != nil {
cand := heaps[curr]
heaps[curr] = pop(heaps[curr])
if find(cand.u) == curr {
continue
}
minEdge = cand
break
}
if minEdge == nil {
break
}
enter[curr] = minEdge
inEdge[minEdge.v] = minEdge
nxt := find(minEdge.u)
if visited[nxt] == 2 {
break
} else if visited[nxt] == 0 {
visited[nxt] = 1
path = append(path, nxt)
curr = nxt
} else if visited[nxt] == 1 {
idx := -1
for j := 0; j < len(path); j++ {
if path[j] == nxt {
idx = j
break
}
}
compId++
newC := compId
for j := idx; j < len(path); j++ {
c := path[j]
parent[c] = newC
lazyVal := -enter[c].w
if heaps[c] != nil {
apply(heaps[c], lazyVal)
heaps[newC] = merge(heaps[newC], heaps[c])
}
}
path = path[:idx]
path = append(path, newC)
visited[newC] = 1
curr = newC
}
}
for _, c := range path {
visited[c] = 2
}
}
ans := []int{}
for i := 2; i <= n; i++ {
if inEdge[i] != nil && edges[inEdge[i].id].w == 1 {
ans = append(ans, inEdge[i].id)
}
}
if len(ans) == 0 {
fmt.Fprintln(out, 0)
} else {
fmt.Fprintln(out, len(ans))
for i, id := range ans {
if i > 0 {
fmt.Fprint(out, " ")
}
fmt.Fprint(out, id)
}
fmt.Fprintln(out)
}
}