For problem statement at 0-999/700-799/700-709/704/problemD.txt this is a correct solution, but verifier at 0-999/700-799/700-709/704/verifierD.go ends with All tests passed can you fix the verifier? ```go
package main
import (
"bufio"
"fmt"
"os"
"strconv"
)
var scanner *bufio.Scanner
func init() {
scanner = bufio.NewScanner(os.Stdin)
scanner.Split(bufio.ScanWords)
buf := make([]byte, 1024*1024)
scanner.Buffer(buf, 10*1024*1024)
}
func nextInt() int {
scanner.Scan()
res, _ := strconv.Atoi(scanner.Text())
return res
}
const INF = 1e9
type Point struct{ x, y int }
type Constraint struct{ t, l, d int }
type Edge struct {
to, cap, flow, rev, id int
}
var g [][]Edge
var level []int
var ptr []int
func addEdge(u, v, cap, id int) {
g[u] = append(g[u], Edge{v, cap, 0, len(g[v]), id})
g[v] = append(g[v], Edge{u, 0, 0, len(g[u]) - 1, -1})
}
var q []int
func bfs(s, t int) bool {
for i := range level {
level[i] = -1
}
level[s] = 0
q = append(q[:0], s)
for len(q) > 0 {
v := q[0]
q = q[1:]
for _, e := range g[v] {
if e.cap-e.flow > 0 && level[e.to] == -1 {
level[e.to] = level[v] + 1
q = append(q, e.to)
}
}
}
return level[t] != -1
}
func dfs(v, t, pushed int) int {
if pushed == 0 {
return 0
}
if v == t {
return pushed
}
for ; ptr[v] < len(g[v]); ptr[v]++ {
e := &g[v][ptr[v]]
tr := e.to
if level[v]+1 != level[tr] || e.cap-e.flow == 0 {
continue
}
push := pushed
if e.cap-e.flow < push {
push = e.cap - e.flow
}
p := dfs(tr, t, push)
if p == 0 {
continue
}
e.flow += p
g[tr][e.rev].flow -= p
return p
}
return 0
}
func dinic(s, t int) int {
flow := 0
for bfs(s, t) {
for i := range ptr {
ptr[i] = 0
}
for {
pushed := dfs(s, t, INF)
if pushed == 0 {
break
}
flow += pushed
}
}
return flow
}
func main() {
if !scanner.Scan() {
return
}
N, _ := strconv.Atoi(scanner.Text())
M := nextInt()
r := nextInt()
b := nextInt()
shields := make([]Point, N)
mapX := make(map[int]int)
mapY := make(map[int]int)
for i := 0; i < N; i++ {
shields[i].x = nextInt()
shields[i].y = nextInt()
if _, ok := mapX[shields[i].x]; !ok {
mapX[shields[i].x] = len(mapX) + 1
}
if _, ok := mapY[shields[i].y]; !ok {
mapY[shields[i].y] = len(mapY) + 1
}
}
constraints := make([]Constraint, M)
for i := 0; i < M; i++ {
constraints[i].t = nextInt()
constraints[i].l = nextInt()
constraints[i].d = nextInt()
}
Kx := len(mapX)
Ky := len(mapY)
degX := make([]int, Kx+1)
degY := make([]int, Ky+1)
minDx := make([]int, Kx+1)
minDy := make([]int, Ky+1)
for i := 1; i <= Kx; i++ {
minDx[i] = INF
}
for i := 1; i <= Ky; i++ {
minDy[i] = INF
}
for _, p := range shields {
degX[mapX[p.x]]++
degY[mapY[p.y]]++
}
for _, c := range constraints {
if c.t == 1 {
if id, ok := mapX[c.l]; ok {
if c.d < minDx[id] {
minDx[id] = c.d
}
}
} else {
if id, ok := mapY[c.l]; ok {
if c.d < minDy[id] {
minDy[id] = c.d
}
}
}
}
S := 0
T := Kx + Ky + 1
SS := T + 1
TT := T + 2
numNodes := TT + 1
g = make([][]Edge, numNodes)
g[S] = make([]Edge, 0, Kx+2)
g[T] = make([]Edge, 0, Ky+2)
for i := 1; i <= Kx; i++ {
g[i] = make([]Edge, 0, degX[i]+2)
}
for j := 1; j <= Ky; j++ {
g[Kx+j] = make([]Edge, 0, degY[j]+2)
}
g[SS] = make([]Edge, 0, numNodes)
g[TT] = make([]Edge, 0, numNodes)
level = make([]int, numNodes)
ptr = make([]int, numNodes)
D := make([]int, numNodes)
addBounds := func(u, v, L, R int) {
addEdge(u, v, R-L, -1)
D[v] += L
D[u] -= L
}
for i := 1; i <= Kx; i++ {
diff := degX[i] - minDx[i]
L := 0
if diff > 0 {
L = (diff + 1) / 2
}
R := (degX[i] + minDx[i]) / 2
if R > degX[i] {
R = degX[i]
}
if L > R {
fmt.Println("-1")
return
}
addBounds(S, i, L, R)
}
for j := 1; j <= Ky; j++ {
diff := degY[j] - minDy[j]
L := 0
if diff > 0 {
L = (diff + 1) / 2
}
R := (degY[j] + minDy[j]) / 2
if R > degY[j] {
R = degY[j]
}
if L > R {
fmt.Println("-1")
return
}
addBounds(Kx+j, T, L, R)
}
for k, p := range shields {
u := mapX[p.x]
v := Kx + mapY[p.y]
addEdge(u, v, 1, k)
}
sumDemands := 0
for i := 0; i < numNodes; i++ {
if D[i] > 0 {
addEdge(SS, i, D[i], -1)
sumDemands += D[i]
} else if D[i] < 0 {
addEdge(i, TT, -D[i], -1)
}
}
if r < b {
addEdge(T, S, INF, -2)
idxTS := len(g[T]) - 1
idxST := len(g[S]) - 1
dinic(SS, TT)
tot := 0
for _, e := range g[SS] {
tot += e.flow
}
if tot != sumDemands {
fmt.Println("-1")
return
}
g[T][idxTS].cap = 0
g[T][idxTS].flow = 0
g[S][idxST].cap = 0
g[S][idxST].flow = 0
dinic(S, T)
} else {
dinic(SS, TT)
addEdge(T, S, INF, -2)
dinic(SS, TT)
tot := 0
for _, e := range g[SS] {
tot += e.flow
}
if tot != sumDemands {
fmt.Println("-1")
return
}
}
ans := make([]byte, N)
redCount := 0
for u := 1; u <= Kx; u++ {
for _, e := range g[u] {
if e.id >= 0 {
if e.flow == 1 {
ans[e.id] = 'r'
redCount++
} else {
ans[e.id] = 'b'
}
}
}
}
cost := int64(redCount)*int64(r) + int64(N-redCount)*int64(b)
fmt.Println(cost)
fmt.Println(string(ans))
}
```