For problem statement at 1000-1999/1300-1399/1360-1369/1368/problemE.txt this is a correct solution, but verifier at 1000-1999/1300-1399/1360-1369/1368/verifierE.go ends with wrong answer on test 2
input:
1
5 5
3 5
2 5
1 5
3 4
4 5
expected:
1
5
got:
2
4 5
exit status 1 can you fix the verifier? ```go
package main
import (
"bufio"
"os"
"strconv"
)
func main() {
// Configure scanner for fast I/O
scanner := bufio.NewScanner(os.Stdin)
scanner.Split(bufio.ScanWords)
writer := bufio.NewWriter(os.Stdout)
defer writer.Flush()
if !scanner.Scan() {
return
}
t, _ := strconv.Atoi(scanner.Text())
for i := 0; i < t; i++ {
solve(scanner, writer)
}
}
func solve(sc *bufio.Scanner, wr *bufio.Writer) {
if !sc.Scan() {
return
}
n, _ := strconv.Atoi(sc.Text())
if !sc.Scan() {
return
}
m, _ := strconv.Atoi(sc.Text())
adj := make([][]int, n+1)
for i := 0; i < m; i++ {
sc.Scan()
u, _ := strconv.Atoi(sc.Text())
sc.Scan()
v, _ := strconv.Atoi(sc.Text())
adj[u] = append(adj[u], v)
}
// Compute L[u]: length of the longest path ending at u
// Since x < y for all edges x->y, we can iterate 1 to n
L := make([]int, n+1)
for i := 1; i <= n; i++ {
if L[i] == 0 {
L[i] = 1
}
for _, v := range adj[i] {
if L[i]+1 > L[v] {
L[v] = L[i] + 1
}
}
}
// Precompute bitmasks of neighbors' L[u]%7
mod := make([]int, n+1)
inM := make([]int, n+1)
outM := make([]int, n+1)
for i := 1; i <= n; i++ {
mod[i] = L[i] % 7
}
for u := 1; u <= n; u++ {
ub := 1 << mod[u]
for _, v := range adj[u] {
outM[u] |= (1 << mod[v])
inM[v] |= ub
}
}
// We need to keep at least 3/7 of nodes
target := (3*n + 6) / 7
bestMask := 0
// Try all possible masks of length modulo 7
// There are 2^7 = 128 masks
for mk := 0; mk < 128; mk++ {
cnt := 0
for u := 1; u <= n; u++ {
if (mk>>mod[u])&1 == 1 {
// We keep u if it's in the mask, unless it's a "transit" node
// A transit node is one that has both potential incoming and outgoing edges
// from/to nodes allowed by the mask.
if (inM[u]&mk) != 0 && (outM[u]&mk) != 0 {
continue
}
cnt++
}
}
if cnt >= target {
bestMask = mk
break
}
}
// Identify removed spots based on the best mask
removed := make([]int, 0, n)
for u := 1; u <= n; u++ {
keep := false
if (bestMask>>mod[u])&1 == 1 {
// Same check as above
if !((inM[u]&bestMask) != 0 && (outM[u]&bestMask) != 0) {
keep = true
}
}
if !keep {
removed = append(removed, u)
}
}
// Output result
wr.WriteString(strconv.Itoa(len(removed)))
wr.WriteByte('\n')
for i, v := range removed {
if i > 0 {
wr.WriteByte(' ')
}
wr.WriteString(strconv.Itoa(v))
}
wr.WriteByte('\n')
}
```