Submission #59181534
Source Code Expand
Copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
package main
import (
"bufio"
"fmt"
stdio "io"
"os"
"strconv"
)
var io *Iost
type Iost struct {
Scanner *bufio.Scanner
Writer *bufio.Writer
}
func NewIost(fp stdio.Reader, wfp stdio.Writer) *Iost {
const BufSize = 2000005
scanner := bufio.NewScanner(fp)
scanner.Split(bufio.ScanWords)
scanner.Buffer(make([]byte, BufSize), BufSize)
return &Iost{Scanner: scanner, Writer: bufio.NewWriter(wfp)}
}
func (io *Iost) Text() string {
if !io.Scanner.Scan() {
panic("scan failed")
}
return io.Scanner.Text()
}
func (io *Iost) Atoi(s string) int { x, _ := strconv.Atoi(s); return x }
func (io *Iost) Atoi64(s string) int64 { x, _ := strconv.ParseInt(s, 10, 64); return x }
func (io *Iost) Atof64(s string) float64 { x, _ := strconv.ParseFloat(s, 64); return x }
func (io *Iost) NextInt() int { return io.Atoi(io.Text()) }
func (io *Iost) NextInt64() int64 { return io.Atoi64(io.Text()) }
func (io *Iost) NextFloat64() float64 { return io.Atof64(io.Text()) }
func (io *Iost) Print(x ...interface{}) { fmt.Fprint(io.Writer, x...) }
func (io *Iost) Printf(s string, x ...interface{}) { fmt.Fprintf(io.Writer, s, x...) }
func (io *Iost) Println(x ...interface{}) { fmt.Fprintln(io.Writer, x...) }
const INF int = 1e18
type TrieNode struct {
PreCount int
WordCount int
MinLen int
Parent *TrieNode
Children map[byte]*TrieNode
}
func NewTrieNode(parent *TrieNode) *TrieNode {
return &TrieNode{
MinLen: INF,
Parent: parent,
Children: make(map[byte]*TrieNode),
}
}
type Trie struct {
root *TrieNode
}
func NewTrie() *Trie {
return &Trie{
root: NewTrieNode(nil),
}
}
func (t *Trie) Insert(s []byte) {
if len(s) == 0 {
return
}
root := t.root
for i := 0; i < len(s); i++ {
char := s[i]
if _, ok := root.Children[char]; !ok {
root.Children[char] = NewTrieNode(root)
}
root.Children[char].PreCount++
root = root.Children[char]
root.MinLen = min(root.MinLen, len(s))
}
root.WordCount++
}
func main() {
in := os.Stdin
out := os.Stdout
io = NewIost(in, out)
defer func() {
io.Writer.Flush()
}()
N := io.NextInt()
words := make([]string, N)
for i := 0; i < N; i++ {
words[i] = io.Text()
}
trie := NewTrie()
query := func(s []byte) int {
res := len(s)
root := trie.root
for i := 0; i < len(s); i++ {
char := s[i]
if _, ok := root.Children[char]; !ok {
return res
}
root = root.Children[char]
if root.PreCount > 0 {
lcp := i + 1
res = min(res, root.MinLen+len(s)-2*lcp)
}
}
return res
}
for i := 0; i < N; i++ {
io.Println(query([]byte(words[i])))
trie.Insert([]byte(words[i]))
}
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min32(a, b int32) int32 {
if a < b {
return a
}
return b
}
func max32(a, b int32) int32 {
if a > b {
return a
}
return b
}
func mins(nums ...int) int {
res := nums[0]
for _, num := range nums {
if num < res {
res = num
}
}
return res
}
func maxs(nums ...int) int {
res := nums[0]
for _, num := range nums {
if num > res {
res = num
}
}
return res
}
Submission Info
Submission Time |
|
Task |
G - Edit to Match |
User |
caomeinaixi |
Language |
Go (go 1.20.6) |
Score |
575 |
Code Size |
3401 Byte |
Status |
AC |
Exec Time |
63 ms |
Memory |
42100 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
575 / 575 |
Status |
|
|
Set Name |
Test Cases |
Sample |
00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt |
All |
00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_00.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt, 01_random_24.txt, 01_random_25.txt, 01_random_26.txt, 01_random_27.txt, 01_random_28.txt, 01_random_29.txt, 01_random_30.txt, 01_random_31.txt, 01_random_32.txt, 01_random_33.txt, 01_random_34.txt, 01_random_35.txt, 01_random_36.txt |
Case Name |
Status |
Exec Time |
Memory |
00_sample_00.txt |
AC |
0 ms |
1620 KB |
00_sample_01.txt |
AC |
0 ms |
1604 KB |
00_sample_02.txt |
AC |
0 ms |
1604 KB |
01_random_00.txt |
AC |
58 ms |
41820 KB |
01_random_01.txt |
AC |
58 ms |
41980 KB |
01_random_02.txt |
AC |
62 ms |
41848 KB |
01_random_03.txt |
AC |
62 ms |
41848 KB |
01_random_04.txt |
AC |
62 ms |
41880 KB |
01_random_05.txt |
AC |
58 ms |
42100 KB |
01_random_06.txt |
AC |
44 ms |
5452 KB |
01_random_07.txt |
AC |
63 ms |
41804 KB |
01_random_08.txt |
AC |
60 ms |
41960 KB |
01_random_09.txt |
AC |
59 ms |
41964 KB |
01_random_10.txt |
AC |
63 ms |
42012 KB |
01_random_11.txt |
AC |
60 ms |
41964 KB |
01_random_12.txt |
AC |
62 ms |
41716 KB |
01_random_13.txt |
AC |
63 ms |
41004 KB |
01_random_14.txt |
AC |
36 ms |
13472 KB |
01_random_15.txt |
AC |
22 ms |
3388 KB |
01_random_16.txt |
AC |
23 ms |
3144 KB |
01_random_17.txt |
AC |
63 ms |
41816 KB |
01_random_18.txt |
AC |
35 ms |
22272 KB |
01_random_19.txt |
AC |
29 ms |
15756 KB |
01_random_20.txt |
AC |
26 ms |
12496 KB |
01_random_21.txt |
AC |
13 ms |
2864 KB |
01_random_22.txt |
AC |
13 ms |
2648 KB |
01_random_23.txt |
AC |
13 ms |
2576 KB |
01_random_24.txt |
AC |
14 ms |
2272 KB |
01_random_25.txt |
AC |
16 ms |
2560 KB |
01_random_26.txt |
AC |
18 ms |
2728 KB |
01_random_27.txt |
AC |
42 ms |
5452 KB |
01_random_28.txt |
AC |
35 ms |
4068 KB |
01_random_29.txt |
AC |
37 ms |
5740 KB |
01_random_30.txt |
AC |
50 ms |
12192 KB |
01_random_31.txt |
AC |
48 ms |
18848 KB |
01_random_32.txt |
AC |
13 ms |
2712 KB |
01_random_33.txt |
AC |
13 ms |
2716 KB |
01_random_34.txt |
AC |
14 ms |
2720 KB |
01_random_35.txt |
AC |
13 ms |
2712 KB |
01_random_36.txt |
AC |
34 ms |
5424 KB |