← Home
For problem statement at 1000-1999/1300-1399/1360-1369/1368/problemG.txt this is a correct solution, but verifier at 1000-1999/1300-1399/1360-1369/1368/verifierG.go ends with candidate runtime error on test 1: exit status 2
input:
 4 1
0
0
0
0


exit status 1 can you fix the verifier? package main

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

type Event struct {
	x   int
	y1  int
	y2  int
	val int
}

var cnt []int
var length []int

func update(node, l, r, ql, qr, val int) {
	if ql <= l && r <= qr {
		cnt[node] += val
	} else {
		mid := (l + r) / 2
		if ql <= mid {
			update(2*node, l, mid, ql, qr, val)
		}
		if qr > mid {
			update(2*node+1, mid+1, r, ql, qr, val)
		}
	}
	if cnt[node] > 0 {
		length[node] = r - l + 1
	} else if l == r {
		length[node] = 0
	} else {
		length[node] = length[2*node] + length[2*node+1]
	}
}

func processGraph(target []int) ([]int, []int, []int, int) {
	N := len(target) - 1
	rep := make([]int, N+1)
	for i := 0; i <= N; i++ {
		rep[i] = i
	}
	vis := make([]int, N+1)
	for i := 0; i <= N; i++ {
		if vis[i] == 0 {
			curr := i
			for vis[curr] == 0 {
				vis[curr] = 1
				curr = target[curr]
			}
			if vis[curr] == 1 {
				cs := curr
				rep[curr] = cs
				curr = target[curr]
				for curr != cs {
					rep[curr] = cs
					curr = target[curr]
				}
			}
			curr = i
			for vis[curr] == 1 {
				vis[curr] = 2
				curr = target[curr]
			}
		}
	}

	adj := make([][]int, N+1)
	for i := 0; i <= N; i++ {
		u := i
		v := target[i]
		if rep[u] != rep[v] {
			adj[rep[v]] = append(adj[rep[v]], rep[u])
		}
	}

	in := make([]int, N+1)
	out := make([]int, N+1)
	timer := 0
	var dfs func(int)
	dfs = func(u int) {
		timer++
		in[u] = timer
		for _, v := range adj[u] {
			dfs(v)
		}
		out[u] = timer
	}
	for i := 0; i <= N; i++ {
		if rep[i] == i {
			dfs(i)
		}
	}
	return in, out, rep, timer
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	var n, m int
	fmt.Fscanf(reader, "%d %d\n", &n, &m)

	board := make([]string, n)
	for i := 0; i < n; i++ {
		fmt.Fscanf(reader, "%s\n", &board[i])
	}

	NCells := n * m / 2
	idB := make([][]int, n)
	idW := make([][]int, n)
	for i := 0; i < n; i++ {
		idB[i] = make([]int, m)
		idW[i] = make([]int, m)
		for j := 0; j < m; j++ {
			idB[i][j] = -1
			idW[i][j] = -1
		}
	}

	cntB, cntW := 0, 0
	for r := 0; r < n; r++ {
		for c := 0; c < m; c++ {
			if (r+c)%2 == 0 {
				idB[r][c] = cntB
				cntB++
			} else {
				idW[r][c] = cntW
				cntW++
			}
		}
	}

	targetB := make([]int, NCells+1)
	targetW := make([]int, NCells+1)
	for i := 0; i <= NCells; i++ {
		targetB[i] = NCells
		targetW[i] = NCells
	}

	type Domino struct{ b, w int }
	doms := make([]Domino, 0, NCells)

	for r := 0; r < n; r++ {
		for c := 0; c < m; c++ {
			tr, tc := r, c
			ch := board[r][c]
			if ch == 'U' {
				tr += 2
			} else if ch == 'D' {
				tr -= 2
			} else if ch == 'L' {
				tc += 2
			} else if ch == 'R' {
				tc -= 2
			}

			isB := (r+c)%2 == 0
			if tr >= 0 && tr < n && tc >= 0 && tc < m {
				if isB {
					targetB[idB[r][c]] = idB[tr][tc]
				} else {
					targetW[idW[r][c]] = idW[tr][tc]
				}
			}

			if ch == 'U' {
				b, w := idB[r][c], idW[r+1][c]
				if !isB {
					b, w = idB[r+1][c], idW[r][c]
				}
				doms = append(doms, Domino{b, w})
			} else if ch == 'L' {
				b, w := idB[r][c], idW[r][c+1]
				if !isB {
					b, w = idB[r][c+1], idW[r][c]
				}
				doms = append(doms, Domino{b, w})
			}
		}
	}

	inB, outB, repB, _ := processGraph(targetB)
	inW, outW, repW, timerW := processGraph(targetW)

	events := make([]Event, 0, 2*len(doms))
	for _, d := range doms {
		x1 := inB[repB[d.b]]
		x2 := outB[repB[d.b]]
		y1 := inW[repW[d.w]]
		y2 := outW[repW[d.w]]
		events = append(events, Event{x1, y1, y2, 1})
		events = append(events, Event{x2 + 1, y1, y2, -1})
	}

	sort.Slice(events, func(i, j int) bool {
		return events[i].x < events[j].x
	})

	cnt = make([]int, 4*(timerW+5))
	length = make([]int, 4*(timerW+5))

	ans := int64(0)
	prevX := events[0].x
	ptr := 0
	for ptr < len(events) {
		currX := events[ptr].x
		ans += int64(length[1]) * int64(currX-prevX)
		prevX = currX
		for ptr < len(events) && events[ptr].x == currX {
			update(1, 1, timerW, events[ptr].y1, events[ptr].y2, events[ptr].val)
			ptr++
		}
	}

	fmt.Println(ans)
}