QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#810274#80. Gluing PicturesSGColinAC ✓14ms34420kbC++20964b2024-12-11 20:50:282024-12-11 20:50:48

Judging History

你现在查看的是最新测评结果

  • [2024-12-11 20:50:48]
  • 评测
  • 测评结果:AC
  • 用时:14ms
  • 内存:34420kb
  • [2024-12-11 20:50:28]
  • 提交

answer

#include<cstdio>
using namespace std;
const int maxn=200000,maxt=maxn<<1,maxi=26;

int n,te;char s[maxn+5],t[maxn+5];
int pl,ro,son[maxt+5][maxi],fai[maxt+5],MAX[maxt+5];

inline int newnode() {pl++;return pl;}
int Extend(int p,int c){
	int np=newnode();MAX[np]=MAX[p]+1;
	while (p && !son[p][c]) son[p][c]=np,p=fai[p];
	if (!p) {fai[np]=ro;return np;}
	int q=son[p][c];if (MAX[p]+1==MAX[q]) {fai[np]=q;return np;}
	int nq=newnode();MAX[nq]=MAX[p]+1;
	for (int i=0;i<maxi;i++) son[nq][i]=son[q][i];
	fai[nq]=fai[q];fai[q]=fai[np]=nq;
	while (p && son[p][c]==q) son[p][c]=nq,p=fai[p];
	return np;
}
int main(){
	scanf("%s",s+1);ro=newnode();
	for (int i=1,p=ro;s[i];i++) p=Extend(p,s[i]-'A');
	for (scanf("%d",&te);te;te--){
		scanf("%s",t+1);
		int ans=0;
		for (int i=1,p=ro;t[i];i++){
			p=son[p][t[i]-'A'];
			if (!p){
				p=son[ro][t[i]-'A'];ans++;
				if (!p) {ans=-2;break;}
			}
		}
		printf("%d\n",ans+1);
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3700kb

input:

MONTEVIDEO
4
DEMONIO
MONTE
EDIT
WON

output:

4
1
4
-1

result:

ok 4 lines

Test #2:

score: 0
Accepted
time: 12ms
memory: 31000kb

input:

PMZTZCUOYRAGXNGRENYXYCCPULCJLITRFEDMDJPMOUDGQPLOWXFHWNVWMVJGVNZLRGLRDWISNZHZOZOIYNYHEWNLJFELOLASYVUDEMGHVLGQHGQNCGQLIAAEGIDCSXFTIUOYXMORUBLKOXQROPWRTAFXXOJNREOZMUCEAQESMHBTQAEPITRPCFQKSWAOMHTIHJRBKHJYOBJTKOPGYIZVJJFCGIKZDLSVGCQDTKGRXYECUOQGCISMBLKGHXXWLFCGQWLMPUKZCWLUMSOOIHFEKUJSPTBUCNFTFDNNUNDTKDCK...

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 14ms
memory: 1596kb

input:

A
199999
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 199999 lines

Test #4:

score: 0
Accepted
time: 0ms
memory: 1644kb

input:

BGTIWPXFVZAUS
26
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z

output:

1
1
-1
-1
-1
1
1
-1
1
-1
-1
-1
-1
-1
-1
1
-1
-1
1
1
1
1
1
1
-1
1

result:

ok 26 lines

Test #5:

score: 0
Accepted
time: 0ms
memory: 1552kb

input:

ADVXIFPRSUQHC
26
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z

output:

1
-1
1
1
-1
1
-1
1
1
-1
-1
-1
-1
-1
-1
1
1
1
1
-1
1
1
-1
1
-1
-1

result:

ok 26 lines

Test #6:

score: 0
Accepted
time: 0ms
memory: 1556kb

input:

FCERYGBJXKSIT
26
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z

output:

-1
1
1
-1
1
1
1
-1
1
1
1
-1
-1
-1
-1
-1
-1
1
1
1
-1
-1
-1
1
1
-1

result:

ok 26 lines

Test #7:

score: 0
Accepted
time: 0ms
memory: 1644kb

input:

VSHZPYTLRXKDO
26
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z

output:

-1
-1
-1
1
-1
-1
-1
1
-1
-1
1
1
-1
-1
1
1
-1
1
1
1
-1
1
-1
1
1
1

result:

ok 26 lines

Test #8:

score: 0
Accepted
time: 0ms
memory: 1628kb

input:

FQZMJLPDSOXAK
26
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z

output:

1
-1
-1
1
-1
1
-1
-1
-1
1
1
1
1
-1
1
1
1
-1
1
-1
-1
-1
-1
1
-1
1

result:

ok 26 lines

Test #9:

score: 0
Accepted
time: 0ms
memory: 1620kb

input:

TNHHGYVHFKSDSMH
8
VHFKS
DSNHHGYVHFTNFKSD
TNNHHGYNHHTN
HGVVHFKSDSGYV
HFKSTNHHGYVTNHFKSHHGY
VHSDSMHKSSDSM
H
HGYVHFKHHGYVHNHHHGY

output:

1
4
4
4
5
4
1
4

result:

ok 8 lines

Test #10:

score: 0
Accepted
time: 0ms
memory: 12688kb

input:

ABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABC...

output:

99999

result:

ok single line: '99999'

Test #11:

score: 0
Accepted
time: 0ms
memory: 1992kb

input:

ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABABBABAABBAABABBABAABABBAABBABAABABBABAABBAABABBAABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABABBABAABBAABABBAABBABAABBAABABBABAABABBAABBABAABABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABABBABAABBAABABBABAABABBAABBABAABABBABAABBAABABBAABBABAABBAAB...

output:

2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 2038 lines

Test #12:

score: 0
Accepted
time: 0ms
memory: 1628kb

input:

SANTIAGO
3
TITA
SANTIAGO
NAS

output:

3
1
3

result:

ok 3 lines

Test #13:

score: 0
Accepted
time: 3ms
memory: 34420kb

input:

ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

364

result:

ok single line: '364'

Test #14:

score: 0
Accepted
time: 1ms
memory: 4232kb

input:

ABCDEFGHIJKLMNOPQRSTUVWXYZJJJJJJJJJJJJJJJJIKJJJJJJJJJJJJJXKHJJJJJJJJJJJJJXKGJJJJJJJJJJJJJXJINJJJJJJJJJJJJXKIIIKJKJJJJJKKLXIJLJJKJLIKJKJJLXKKIHIIKKKIKJJJIXIKHKJJKIJJLJJJJXIJIHKIJIKIKIKIJXJJIJJJJJJJIMJJJXIIJJKJIJKIHIJKHXJJKKKJHJJLKHJIJXIJJIKKKIIILHIJJXKIKJIKIKJKIJHJJXKJKIKJGKJHKKKJIXKHHLIJJIKILJIKIXIK...

output:

2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
...

result:

ok 300 lines

Test #15:

score: 0
Accepted
time: 1ms
memory: 2416kb

input:

ABCDEFGHIJKLMNOPQRSTUVWXYZJJJJJJJJJJJJJJJJIKJJJJJJJJJJJJJXKHJJJJJJJJJJJJJXKGJJJJJJJJJJJJJXJINJJJJJJJJJJJJXJLIJJKLJJJJJKIJXKKJIIJIJLIJJJMKXIILHKIJIJJJKJILXLKHKJJJJKJKIJKKXMJJIJJJKIKJLKJKXIJJJJJJJIKJJJJJXKJJJGJJIKIIILJKXKJIHJILIJIJJJHJXJIJKLKIKHJKJIKKXIJIKHKJJIIKIKJIXJJLJKHKJJJJIHLJXKJIJLJIIJJIJKKJXJJ...

output:

2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
...

result:

ok 300 lines

Test #16:

score: 0
Accepted
time: 3ms
memory: 8900kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

result:

ok 17 lines

Test #17:

score: 0
Accepted
time: 2ms
memory: 2656kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

result:

ok 60 lines

Test #18:

score: 0
Accepted
time: 4ms
memory: 17972kb

input:

ABABBBAABABBBAAABAAABAAABBABBAAAABAABBBBBABBBABABBAABBBBABAABABABAAABAABAABABBBABBAAAAAAAAABBBBAABBAABAAABAABABABBABABABAABAAAABBBBBBABBABAABBAABBBABAABBBAABAABABBABBABABABBAABBBBAABABBBAABABBBBAAABBBBAABBABABABAABAAABBAAABABAABBAABAAABABBABBBAABBABAABAABBBBBABABBBBABABAABAABABBABAABBBBABBBABBBAAABB...

output:

149
524
2
112
282
40
42
143
350
1247
581
164
369
410
457
238
171
17
386
210

result:

ok 20 lines

Test #19:

score: 0
Accepted
time: 4ms
memory: 10564kb

input:

BABBABABBABABBBAABBAAABBABBBBBBBABBAABBABAABBAAABBABBBABAAAABAAAABABABBAABAAAABAAABAABABAAAAABBBABABBAABABAABABBABAABABBAAABABABAAABABBAABBBABBAABBABBBBAAAAAABBBAABABBBAAABBBBBABBBAABBBABBABBAAAAAAABABAAAABAABAAABAAABAABAAABABBABBAAAABBBAABBBBABAAABAABBBABAAABBAAAABBABAABABBABBABABABAAAAAABAAABBAABA...

output:

1
2
1
2
1
1
1
1
1
1
1
4
1
1
2
3
2
3
2
1
1
1
2
1
2
2
1
4
2
1
3
2
4
1
3
3
2
1
1
3
2
1
1
1
1
3
1
1
4
1
1
1
2
3
4
1
2
7
1
1
1
3
1
1
2
2
1
1
3
1
1
4
2
3
1
1
1
2
1
4
1
1
1
1
1
4
2
1
3
1
2
1
2
1
2
1
3
3
1
1

result:

ok 100 lines

Test #20:

score: 0
Accepted
time: 2ms
memory: 6332kb

input:

AAABAABBABBAAAAAABBBABAAABABBBBBAABAABBBABAABBBABBBAABBBBBBABBABBBBBBBAABAABBBBBAABAAAAAABABABAAABAABBABBABBAAABABAABBAAAABABABAAAAABAABBAABABABAAAABABAABBAABBAABAABABABBAAABAAABBABBBABBABAABBAABBBBABABAAAABBAAAABAAAAABBBAAAABBBBABBBBAABAAABAABBAAAABBBABAAAAAAABBABAAABBBABBBABAABBBAABAAAABBABBABAAAA...

output:

3
1
2
2
1
2
5
1
1
2
1
1
1
1
1
1
4
1
4
2
1
2
2
1
2
1
3
1
2
3
1
1
4
1
3
1
2
1
3
1
1
1
2
1
1
4
1
2
3
1
1
1
1
1
2
1
3
1
3
1
1
4
1
2
3
1
3
3
2
1
2
1
1
2
2
2
1
5
2
2
3
6
2
1
1
2
1
2
2
4
3
2
3
1
3
1
1
1
1
1

result:

ok 100 lines

Test #21:

score: 0
Accepted
time: 1ms
memory: 3448kb

input:

AABAAAAAAAAAABBBAABABBAABBAAABAABAAAABBBAAABAABBBBBABBBAAABABAAABBABAABBBBBABBAABAAABBAABBABAABBAABAAABBBABBBABBBABBAABBBAABABBBBBBAAABBAABAAABBABBAAABAABAABBBBABBAAAABABAAABBBBBAAAABBAAABABABBAABBBAABBAAAAABBAAABABBBBBBBAAAAABABABBABAABBBABBABBABBABAABABBABABAAAABABBBBBBAABABBABABABABAABBBBBBBBBABB...

output:

2
2
3
1
3
1
2
1
2
2
2
1
2
2
1
1
1
1
1
1
1
1
1
3
3
1
3
2
3
2
1
1
1
1
3
4
1
4
1
1
1
5
2
1
1
2
2
2
1
1
1
1
4
1
1
4
1
1
1
6
6
2
2
1
1
2
2
1
2
4
2
1
4
4
2
1
4
1
1
1
1
1
3
2
3
3
2
3
2
1
4
5
1
1
2
2
4
1
1
1

result:

ok 100 lines

Test #22:

score: 0
Accepted
time: 0ms
memory: 4536kb

input:

BBBBAAABAAABABABABABAABAABBABBBABBABAAAABBABABBBABABABBABBBBBBABAABBABBAABBAAABBBBBBABAAABBABBABBABBBAABBABABBBBBBABABBBAAABAABBAAAABBAABBAAAAAABBABBAAABBAABBAABABBBAAABABBABBBABABBBABBBBBABAAABAAAABBBAABAAABBBAABAABAAABBABAAABBBBAABABBABABBABBBBAAABAABBBBBAAABBABABBAAABBAAABBABAABAAABAAABBBAAABABAA...

output:

1
1
4
4
1
1
3
1
3
1
1
2
1
1
1
1
1
1
2
1
1
2
2
1
1
2
1
5
1
2
3
2
1
2
1
1
2
2
1
1
6
1
2
4
2
2
1
4
2
3
2
3
1
6
1
2
1
1
3
4
3
1
1
1
1
4
2
1
10
4
1
1
1
1
2
1
1
1
3
2
2
2
1
1
1
2
3
1
1
1
2
4
2
2
2
4
3
1
1
3

result:

ok 100 lines

Test #23:

score: 0
Accepted
time: 0ms
memory: 1632kb

input:

A
100
A
AA
AAA
AAAA
AAAAA
AAAAAA
AAAAAAA
AAAAAAAA
AAAAAAAAA
AAAAAAAAAA
AAAAAAAAAAA
AAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAAA
AAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAA...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

result:

ok 100 lines

Test #24:

score: 0
Accepted
time: 1ms
memory: 1820kb

input:

A
1
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

-1

result:

ok single line: '-1'