For problem statement at 1000-1999/1100-1199/1100-1109/1100/problemE.txt this is a correct solution, but verifier at 1000-1999/1100-1199/1100-1109/1100/verifierE.go ends with case 1 failed: expected 9 10
4 5 8 12 14 15 20 22 23 25 got 9 17
3 4 8 9 11 12 13 15 17 18 19 20 22 23 25 27 28
exit status 1 can you fix the verifier? package main
import (
"bufio"
"fmt"
"os"
"strconv"
)
type Edge struct {
id int
u int
v int
c int
}
func main() {
scanner := bufio.NewScanner(os.Stdin)
scanner.Split(bufio.ScanWords)
scanner.Buffer(make([]byte, 1024*1024), 1024*1024*10)
if !scanner.Scan() {
return
}
n, _ := strconv.Atoi(scanner.Text())
scanner.Scan()
m, _ := strconv.Atoi(scanner.Text())
edges := make([]Edge, m)
maxC := 0
for i := 0; i < m; i++ {
scanner.Scan()
u, _ := strconv.Atoi(scanner.Text())
scanner.Scan()
v, _ := strconv.Atoi(scanner.Text())
scanner.Scan()
c, _ := strconv.Atoi(scanner.Text())
edges[i] = Edge{id: i + 1, u: u, v: v, c: c}
if c > maxC {
maxC = c
}
}
var check = func(X int) (bool, []int) {
inDegree := make([]int, n+1)
adj := make([][]int, n+1)
for _, e := range edges {
if e.c > X {
adj[e.u] = append(adj[e.u], e.v)
inDegree[e.v]++
}
}
queue := make([]int, 0, n)
for i := 1; i <= n; i++ {
if inDegree[i] == 0 {
queue = append(queue, i)
}
}
count := 0
pos := make([]int, n+1)
for len(queue) > 0 {
u := queue[0]
queue = queue[1:]
pos[u] = count
count++
for _, v := range adj[u] {
inDegree[v]--
if inDegree[v] == 0 {
queue = append(queue, v)
}
}
}
if count < n {
return false, nil
}
return true, pos
}
low := 0
high := maxC
ans := -1
var finalPos []int
for low <= high {
mid := low + (high - low) / 2
ok, pos := check(mid)
if ok {
ans = mid
finalPos = pos
high = mid - 1
} else {
low = mid + 1
}
}
reversed := []int{}
if ans != -1 && finalPos != nil {
for _, e := range edges {
if e.c <= ans {
if finalPos[e.u] > finalPos[e.v] {
reversed = append(reversed, e.id)
}
}
}
}
out := bufio.NewWriter(os.Stdout)
fmt.Fprintf(out, "%d %d\n", ans, len(reversed))
for i, id := range reversed {
if i > 0 {
fmt.Fprint(out, " ")
}
fmt.Fprint(out, id)
}
fmt.Fprintln(out)
out.Flush()
}