← Home
For problem statement at 1000-1999/1300-1399/1320-1329/1322/problemC.txt this is a correct solution, but verifier at 1000-1999/1300-1399/1320-1329/1322/verifierC.go ends with All 100 tests passed can you fix the verifier? package main

import (
	"io"
	"os"
	"sort"
	"strconv"
)

type FastScanner struct {
	data []byte
	idx  int
}

func (fs *FastScanner) NextInt64() int64 {
	data := fs.data
	n := len(data)
	i := fs.idx
	for i < n {
		b := data[i]
		if b >= '0' && b <= '9' {
			break
		}
		i++
	}
	var x int64
	for i < n {
		b := data[i]
		if b < '0' || b > '9' {
			break
		}
		x = x*10 + int64(b-'0')
		i++
	}
	fs.idx = i
	return x
}

func gcd(a, b int64) int64 {
	for b != 0 {
		a, b = b, a%b
	}
	if a < 0 {
		return -a
	}
	return a
}

func splitmix64(x uint64) uint64 {
	x += 0x9e3779b97f4a7c15
	x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9
	x = (x ^ (x >> 27)) * 0x94d049bb133111eb
	return x ^ (x >> 31)
}

type Key struct {
	a uint64
	b uint64
}

func hashSeg(seg []int) Key {
	h1 := uint64(1469598103934665603)
	h2 := uint64(1099511628211)
	for _, v := range seg {
		x := uint64(v + 1)
		z1 := splitmix64(x)
		h1 ^= z1
		h1 *= 1099511628211
		z2 := splitmix64(x ^ 0x9e3779b97f4a7c15)
		h2 ^= z2
		h2 *= 14029467366897019727
	}
	h1 ^= splitmix64(uint64(len(seg)))
	h2 ^= splitmix64(uint64(len(seg)) ^ 0xbf58476d1ce4e5b9)
	return Key{h1, h2}
}

func equalSeg(a, b []int) bool {
	if len(a) != len(b) {
		return false
	}
	for i, x := range a {
		if b[i] != x {
			return false
		}
	}
	return true
}

func main() {
	data, _ := io.ReadAll(os.Stdin)
	fs := FastScanner{data: data}
	t := int(fs.NextInt64())

	var cBuf []int64
	var degBuf, startBuf, curBuf, uBuf, vBuf, flatBuf []int
	var repStartBuf, repLenBuf, nextBuf []int
	var sumBuf []int64

	out := make([]byte, 0, t*4)

	for ; t > 0; t-- {
		n := int(fs.NextInt64())
		m := int(fs.NextInt64())

		if cap(cBuf) < n {
			cBuf = make([]int64, n)
		}
		c := cBuf[:n]
		for i := 0; i < n; i++ {
			c[i] = fs.NextInt64()
		}

		if cap(degBuf) < n {
			degBuf = make([]int, n)
		}
		deg := degBuf[:n]
		for i := 0; i < n; i++ {
			deg[i] = 0
		}

		if cap(uBuf) < m {
			uBuf = make([]int, m)
		}
		if cap(vBuf) < m {
			vBuf = make([]int, m)
		}
		u := uBuf[:m]
		v := vBuf[:m]

		for i := 0; i < m; i++ {
			uu := int(fs.NextInt64()) - 1
			vv := int(fs.NextInt64()) - 1
			u[i] = uu
			v[i] = vv
			deg[vv]++
		}

		if cap(startBuf) < n+1 {
			startBuf = make([]int, n+1)
		}
		start := startBuf[:n+1]
		start[0] = 0
		for i := 0; i < n; i++ {
			start[i+1] = start[i] + deg[i]
		}

		if cap(curBuf) < n {
			curBuf = make([]int, n)
		}
		cur := curBuf[:n]
		copy(cur, start[:n])

		if cap(flatBuf) < m {
			flatBuf = make([]int, m)
		}
		flat := flatBuf[:m]
		for i := 0; i < m; i++ {
			vv := v[i]
			flat[cur[vv]] = u[i]
			cur[vv]++
		}

		gcap := n
		if m < gcap {
			gcap = m
		}
		first := make(map[Key]int, gcap)

		if cap(repStartBuf) < gcap {
			repStartBuf = make([]int, 0, gcap)
		}
		if cap(repLenBuf) < gcap {
			repLenBuf = make([]int, 0, gcap)
		}
		if cap(nextBuf) < gcap {
			nextBuf = make([]int, 0, gcap)
		}
		if cap(sumBuf) < gcap {
			sumBuf = make([]int64, 0, gcap)
		}

		repStart := repStartBuf[:0]
		repLen := repLenBuf[:0]
		next := nextBuf[:0]
		sums := sumBuf[:0]

		for i := 0; i < n; i++ {
			l, r := start[i], start[i+1]
			if l == r {
				continue
			}
			seg := flat[l:r]
			if len(seg) > 1 {
				sort.Ints(seg)
			}
			k := hashSeg(seg)
			head := first[k]
			found := -1
			for idx := head; idx != 0; idx = next[idx-1] {
				j := idx - 1
				if repLen[j] != len(seg) {
					continue
				}
				if equalSeg(flat[repStart[j]:repStart[j]+repLen[j]], seg) {
					found = j
					break
				}
			}
			if found >= 0 {
				sums[found] += c[i]
			} else {
				repStart = append(repStart, l)
				repLen = append(repLen, len(seg))
				sums = append(sums, c[i])
				next = append(next, head)
				first[k] = len(sums)
			}
		}

		repStartBuf = repStart
		repLenBuf = repLen
		nextBuf = next
		sumBuf = sums

		var ans int64
		for _, x := range sums {
			ans = gcd(ans, x)
		}

		out = strconv.AppendInt(out, ans, 10)
		out = append(out, '\n')
	}

	_, _ = os.Stdout.Write(out)
}