For problem statement at 0-999/700-799/760-769/763/problemE.txt this is a correct solution, but verifier at 0-999/700-799/760-769/763/verifierE.go ends with All 45 tests passed. can you fix the verifier? package main
import (
"bytes"
"io"
"os"
"strconv"
)
const B = 10
type Node struct {
l, r int
cnt int
s int
c int
verts [B]int
cls [B]int
}
func find(parent *[20]int, x int) int {
for parent[x] != x {
parent[x] = parent[parent[x]]
x = parent[x]
}
return x
}
func unite(parent *[20]int, x, y int) {
rx := find(parent, x)
ry := find(parent, y)
if rx != ry {
parent[ry] = rx
}
}
func getClass(nd *Node, x int) int {
for i := 0; i < nd.s; i++ {
if nd.verts[i] == x {
return nd.cls[i]
}
}
return -1
}
func merge(a, b Node, edgeMask []uint8, k int) Node {
if a.s == 0 {
return b
}
if b.s == 0 {
return a
}
cA, cB := a.c, b.c
num := cA + cB
var parent [20]int
for i := 0; i < num; i++ {
parent[i] = i
}
aRightStart := a.r - k + 1
if aRightStart < a.l {
aRightStart = a.l
}
bLeftEnd := b.l + k - 1
if bLeftEnd > b.r {
bLeftEnd = b.r
}
for i := 0; i < a.s; i++ {
u := a.verts[i]
if u < aRightStart {
continue
}
cu := a.cls[i]
for j := 0; j < b.s; j++ {
v := b.verts[j]
if v > bLeftEnd {
break
}
d := v - u
if d >= 1 && d <= k && (edgeMask[u]&uint8(1<<uint(d-1))) != 0 {
unite(&parent, cu, cA+b.cls[j])
}
}
}
var seen [20]bool
groups := 0
for i := 0; i < num; i++ {
r := find(&parent, i)
if !seen[r] {
seen[r] = true
groups++
}
}
var c Node
c.l = a.l
c.r = b.r
c.cnt = (a.cnt - cA) + (b.cnt - cB) + groups
totalLen := c.r - c.l + 1
leftNeed := k
if totalLen < leftNeed {
leftNeed = totalLen
}
rightNeed := k
if totalLen < rightNeed {
rightNeed = totalLen
}
leftEnd := c.l + leftNeed - 1
for x := c.l; x <= leftEnd; x++ {
c.verts[c.s] = x
c.s++
}
rightStart := c.r - rightNeed + 1
if rightStart <= leftEnd {
rightStart = leftEnd + 1
}
for x := rightStart; x <= c.r; x++ {
c.verts[c.s] = x
c.s++
}
var roots [B]int
for i := 0; i < c.s; i++ {
x := c.verts[i]
id := -1
if x <= a.r {
id = getClass(&a, x)
} else {
id = cA + getClass(&b, x)
}
root := find(&parent, id)
label := -1
for j := 0; j < c.c; j++ {
if roots[j] == root {
label = j
break
}
}
if label == -1 {
roots[c.c] = root
label = c.c
c.c++
}
c.cls[i] = label
}
return c
}
func query(tree []Node, size, l, r int, edgeMask []uint8, k int) Node {
l = l - 1 + size
r = r - 1 + size
var leftRes, rightRes Node
hasL, hasR := false, false
for l <= r {
if (l & 1) == 1 {
if !hasL {
leftRes = tree[l]
hasL = true
} else {
leftRes = merge(leftRes, tree[l], edgeMask, k)
}
l++
}
if (r & 1) == 0 {
if !hasR {
rightRes = tree[r]
hasR = true
} else {
rightRes = merge(tree[r], rightRes, edgeMask, k)
}
r--
}
l >>= 1
r >>= 1
}
if !hasL {
return rightRes
}
if !hasR {
return leftRes
}
return merge(leftRes, rightRes, edgeMask, k)
}
func main() {
data, _ := io.ReadAll(os.Stdin)
idx := 0
nextInt := func() int {
for idx < len(data) && (data[idx] < '0' || data[idx] > '9') {
idx++
}
val := 0
for idx < len(data) && data[idx] >= '0' && data[idx] <= '9' {
val = val*10 + int(data[idx]-'0')
idx++
}
return val
}
n := nextInt()
k := nextInt()
edgeMask := make([]uint8, n+2)
m := nextInt()
for i := 0; i < m; i++ {
u := nextInt()
v := nextInt()
if u > v {
u, v = v, u
}
d := v - u
if d >= 1 && d <= k {
edgeMask[u] |= uint8(1 << uint(d-1))
}
}
size := 1
for size < n {
size <<= 1
}
tree := make([]Node, size<<1)
for i := 0; i < n; i++ {
var nd Node
nd.l = i + 1
nd.r = i + 1
nd.cnt = 1
nd.s = 1
nd.c = 1
nd.verts[0] = i + 1
nd.cls[0] = 0
tree[size+i] = nd
}
for i := size - 1; i >= 1; i-- {
tree[i] = merge(tree[i<<1], tree[i<<1|1], edgeMask, k)
}
q := nextInt()
var out bytes.Buffer
for i := 0; i < q; i++ {
l := nextInt()
r := nextInt()
res := query(tree, size, l, r, edgeMask, k)
out.WriteString(strconv.Itoa(res.cnt))
out.WriteByte('\n')
}
os.Stdout.Write(out.Bytes())
}