← Home
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())
}