QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#482982#4224. 串zyxawa60 203ms152552kbC++141.1kb2024-07-18 08:29:422024-07-18 08:29:42

Judging History

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

  • [2024-07-18 08:29:42]
  • 评测
  • 测评结果:60
  • 用时:203ms
  • 内存:152552kb
  • [2024-07-18 08:29:42]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
struct node{
	int len,link,son[26];
}t[1000001];
int k,n,ans,tot,lst,siz[1000001],pos[1000001];
char s[500001];
basic_string <int> G[1000001];
void insert(int c){
	int cur=++tot,p=lst;
	t[cur].len=t[p].len+1;
	for(;p!=-1&&!t[p].son[c];p=t[p].link) t[p].son[c]=cur;
	if(p==-1) t[cur].link=0;
	else{
		int q=t[p].son[c];
		if(t[q].len==t[p].len+1) t[cur].link=q;
		else{
			t[++tot]=t[q];
			t[tot].len=t[p].len+1;
			t[cur].link=t[q].link=tot;
			for(;p!=-1&&t[p].son[c]==q;p=t[p].link) t[p].son[c]=tot;
		}
	}
	lst=cur;
}
void dfs(int x){
	for(int y:G[x]) dfs(y),siz[x]+=siz[y],pos[x]=min(pos[x],pos[y]);
}
int main(){
	memset(pos,0x3f,sizeof(pos));
	scanf("%d",&k);
	while(k--){
		scanf("%s",s+1),n=strlen(s+1),ans=n/2,tot=0,t[0].link=-1;
		for(int i=1;i<=n;i++) insert(s[i]-97),siz[lst]++,pos[lst]=i;
		for(int i=1;i<=tot;i++) G[t[i].link]+=i;
		dfs(0);
		for(int i=1;i<=tot;i++) if(siz[i]>1) ans=max(ans,t[i].len+(n-pos[i])/2);
		printf("%d\n",ans);
		for(int i=0;i<=tot;i++) G[i].clear(),pos[i]=1e9,siz[i]=t[i].len=t[i].link=0,memset(t[i].son,0,sizeof(t[i].son));
	}
	return 0;
}

詳細信息

Test #1:

score: 5
Accepted
time: 0ms
memory: 43488kb

input:

5
wwgpdvdwwgpdvdwwgpdvdwwwvdwdww
imeoqomeomqomeommeoqomeomqomem
blmjcxblmjcxlmjlmjcxjcxblmjcxl
exzhdyzhddyzhdedyzhyzhddydyyzd
tsbosqtsbosqtsbossbosqtssqtsbb

output:

23
21
18
15
20

result:

ok 5 lines

Test #2:

score: 0
Wrong Answer
time: 4ms
memory: 41728kb

input:

5
rmgmlkgmlkllklmlkgmgmlklklmlkm
fstnttfttfnttfttfttfttfttttftt
hxiykziykzixiykziyykzixiyiyyky
fbtnfwbtnffwbfbtnfwbtnffwwbtnw
yhdizazyhdidihdidihdizzazyyhdi

output:

17
17
18
21
43

result:

wrong answer 5th lines differ - expected: '17', found: '43'

Test #3:

score: 5
Accepted
time: 4ms
memory: 43400kb

input:

4
skjnitkwybtcsfagbpslfxtijbwjqvskibxqwjmukwybtcsfagbbpslfxtijbwjqvskibxqwjmukwybtcsfagbpslfxtijbwjqvskibxqwjmukwybtcsfagbbpslfxtijbwjqvskibxqwjmukwybtcsfagbbpslukwybtcsfagbbpslfxtijbbbpslukwybtcsfaslfc
ssrpyzpwiydtayxmoddtqksdrhcavtsonldnmujuyzpwiydtayxmoddtqksdrhcavtsoniydtayxmoddtqksdrhwiydtayxmo...

output:

137
112
121
112

result:

ok 4 lines

Test #4:

score: 5
Accepted
time: 3ms
memory: 42320kb

input:

4
oupltnlcbcgntpnkbvktcbcpltnlcbcgpltnlcgpltngntpnlcbcgntpnkbvktcbcpltnlcbcgpltnlnlcbcgpltnlcgpltngntpnlcbcgntpnktngntpnlcbcgntpnkbvktcbcpltnlcbcgpltnlnlcbcgpltnlcgpltngntpnlcbcgntpnlcbcgntlcbcgntpnkbvn
nzmyzhhsoehahmorxpahsoehahmororxpahsoehahmhsoehahmmyzhhsoehahmhahsoehahmororxpahsoehahmhsoehahmmy...

output:

114
130
117
113

result:

ok 4 lines

Test #5:

score: 5
Accepted
time: 2ms
memory: 41764kb

input:

4
wwsqbwicfggaflmvdvegdkclrnybwwsqbwicfggafgdkclrnyaflmvdvegdkclrnybwwsqbwlrnybwwsqbwicfggafgdkclrnyaflmvdvegdkclrnybwwegdknybwwsqybwwsqbwlrnybwwsqbwicfggafgdkclrnyaflmvdvegdkclrnybqbwicfggafgdkclrnyafg
tgloxggsznuxqxggszxggszsznuxqxggszxggszggsznuxqxggsggsznuxqxggszxggszsznuxqxggszxggszggsznuxqxggs...

output:

111
120
112
106

result:

ok 4 lines

Test #6:

score: 5
Accepted
time: 5ms
memory: 43284kb

input:

3
ikcblmcsjillvojwymeimbaeipbhobwwnyaakcsvkghhusduehctjexrtaakewiruishkmewsleodhikrnfaternerxiqhamqutaiazbldrrmaddpidimwxsqwbgedswzowhovibaauncxsthwdvudokzpsfulbtbaapxlexrtaakewiruishkmewsleodhikrnfaternerxiqhamqutaiazbldrrmaddpidimwxsqwbgedswzowhovibaauncxsthwdvudokzpsfulbtbaapxlidimwxsqwbgedswzowh...

output:

638
610
568

result:

ok 3 lines

Test #7:

score: 5
Accepted
time: 0ms
memory: 41644kb

input:

3
gsxasrisfpretvfhxlwnysaarwkvizqrrntjecdltvqmsvvqgsdgkggdcszmtrfkfzwldzxnysgsxasrisfpretvfhxlwgsxasrisfpretvfhqrrntjecdltvqmsvvqgsdgkggdcszmtrfkfzwarwkvizqrrntjecdltvqmsvvqgsdgkggdcszmtrfkfzwldzxnysgsxasrisfpretvjecdltvqmsvvqgsdgkggdcszmtrfkfzwldzxnfkfzwldzxnysgsxasrisfpretvjecdltvqmsvvqgsdgkggdcsz...

output:

582
591
547

result:

ok 3 lines

Test #8:

score: 5
Accepted
time: 8ms
memory: 45676kb

input:

3
aekaabidsppfvwzguexdmycjcqqcxdmycjcqqycjcqexdmycjcqqcxdmycjcqqcxdmycjcqqycjcqevwzguexdmycjcqqcxdmyabidsppfvwzguexdmycjcqqcxdmycjcqqycjcqexdmycjcqqcxdmycjcqqcxdmycjcqqycjcqezguexdmycjcqqcxdmycjcqqycjcqexdmycjcqqcxdmycjcqqcxdmycjcqqycjcqevwzguexdmycjcqqcxdmyxdmycjcqqcxdmycjcqqycjcqexdmycjcqqcxdmycjc...

output:

539
563
520

result:

ok 3 lines

Test #9:

score: 5
Accepted
time: 171ms
memory: 105496kb

input:

4
fqbsybwtrauafctwxtzxmhmelxssvxxapauncqgvqcwxfptcktzyanenlxfguejjhdzjufgmicmptfrfasgcgkqrjxzfcipjoqukvawffkuaqniqgotoylhiignmrevhwrruupzzawbqljitxdhyooixxxlqejxaaouufwvfuzxhigbilkiazqzypkovtnwwbssiqookpnsxvvhhfpjghkezwuushsoilgtbwholuilqdszikiptsvuoqpgxhwisfbwbkkpesawxuvhgfycxuwoklwjvtrpaulbexqlrsh...

output:

187457
187894
187356
187301

result:

ok 4 lines

Test #10:

score: 0
Wrong Answer
time: 97ms
memory: 61524kb

input:

105
iiqnrmmdztbfxwmieuflzvuqveboseucomrfagkbzohyktiqnnbpkyhgciuwoqacerjgxthwjqxtkfjzvnqfnxlpfhnvznxfeglecvcllzhxhszcfphsnvjuewqelnlswxwauylfaufhnejutsngnybuxtaiglaekyeexsmxmrezvpuohjxxjatgttrbetirsmvrehqtawuvlqmuzltllmtgfmjmgrdagytkijfkfagsqumsfidsuyyclhotbrvhrotbzzmgbuyromlvuqnrpntauhvxaqereyvfzjla...

output:

5001
5001
5001
5001
50001
5001
5001
5001
5001
5001
5001
5001
5001
5001
5001
14980
5001
5001
5001
5001
5002
5001
5001
5001
5001
5001
50001
5001
5001
5001
5002
5001
5001
5001
5001
5002
5001
60020
5001
5001
5001
5001
5001
5001
5001
5001
5001
5001
5001
5001
5001
5001
5001
5001
5001
5001
5001
5001
5001
1...

result:

wrong answer 16th lines differ - expected: '5001', found: '14980'

Test #11:

score: 0
Wrong Answer
time: 171ms
memory: 120284kb

input:

1000001
s
o
k
g
r
z
l
d
z
i
n
u
d
j
i
o
k
b
o
s
h
y
w
y
u
k
v
p
d
f
e
x
v
q
d
o
p
r
s
o
z
f
i
e
r
q
s
b
u
i
w
b
g
u
b
a
e
w
p
j
e
v
g
z
l
l
o
c
c
i
q
b
n
b
h
g
t
z
i
p
h
e
s
q
a
u
s
e
s
i
n
w
f
t
y
t
g
o
v
j
w
o
m
l
r
u
s
k
t
c
c
d
i
u
t
i
q
l
m
j
v
b
f
d
w
f
w
c
t
r
l
p
h
y
b
y
u
v
l
n
x
n
s
f
j
n
...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

wrong answer 825258th lines differ - expected: '250001', found: '250003'

Test #12:

score: 0
Wrong Answer
time: 23ms
memory: 46968kb

input:

110
rxxioshkbndigoxntdcejhvoskbndigoxntdcejgoxntdcejhvoskbndigoxbndigoxntdcejhvoskbndigoxntdccejhvoskbndigogoxntdcejgoxntdcejhvoskbndigoxbnejgoxntdcejhvoskbndigoxbndigoxntdcejhvoskbndigoxntdccejhvoskbndigogoxntdcejgoxntdcejhvosxntdcejhvoskbndigoxbndigoxntdcejhvoskbndigoxntdccejhvoskbndigogoxntdcejgo...

output:

629
577
663
560
622
537
11746
11759
625
966
595
537
989
567
539
544
578
562
536
600
572
521
19986
979
952
597
632
957
552
605
980
535
566
559
963
12740
629
548
571
988
641
14356
558
571
598
982
539
645
580
586
967
995
966
597
623
961
589
988
594
582
638
606
11243
954
604
558
588
579
559
627
547
590
...

result:

wrong answer 74th lines differ - expected: '566', found: '1044'

Test #13:

score: 0
Wrong Answer
time: 20ms
memory: 51528kb

input:

105
jlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizo...

output:

993
674
578
520
563
621
39987
623
562
551
650
631
541
598
976
663
578
600
984
556
652
996
560
596
672
964
684
972
613
990
596
551
39989
592
579
552
971
587
958
976
640
641
650
967
997
570
591
523
644
571
951
598
645
601
670
556
536
663
596
719
26336
581
618
658
544
1489
22008
633
979
540
677
539
965...

result:

wrong answer 66th lines differ - expected: '662', found: '1489'

Test #14:

score: 5
Accepted
time: 24ms
memory: 59164kb

input:

5
xsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmn...

output:

59993
31805
31649
59999
35053

result:

ok 5 lines

Test #15:

score: 0
Wrong Answer
time: 21ms
memory: 44160kb

input:

30
qqgcvqshumzfapruaztsztbkdhknlqmegsgekylgmkmobfjceeuezxqcebpqrduyxccjcpqqbefdlqfpubvvymxfnovetrestidxxvnbzsekilcemxbmjaryqofjfjdashxrclsefyqqjswxsykbydcrshczqgaknzermwvsvmkgegeygqahteynlandipovosnbqkvnwfudnabuqddlhbzsdowmfmjtgywwjtmhaikoimkapplzsmrxcpjhdvdjtbievwmxewlokxocobbgoueqkpypkdzgejmzfyxjx...

output:

5409
6422
9965
6171
9985
5656
14898
9965
5246
5788
6213
5511
9988
9994
9991
6384
9982
6431
9993
5763
6489
5902
5343
5847
5849
6573
5863
5737
6460
6527

result:

wrong answer 7th lines differ - expected: '6137', found: '14898'

Test #16:

score: 5
Accepted
time: 203ms
memory: 152300kb

input:

3
pounzdtkokaonqyllykjhhycqxdmmwndkjqlnlxbwzqlpqwcpjnysncilfxzdkenuwbjhakfacsptrukajksxnbksyjykplglopupccpgugzlcllmwgjjhtdhebttpcgfrcuvelczudmyrakngvypqdyufrpwtxbnaykelodhusglsqayoypebnzigqgcokrokbuvsadmsjzkbzkpzzucovnwltyzdrpnvmlnmqbezaqazcsybmcrhpnsjouofleczrplhqrgqhirjarmoudvjtqsjmjqzptzgimnbetrl...

output:

283790
303401
286117

result:

ok 3 lines

Test #17:

score: 0
Wrong Answer
time: 101ms
memory: 100508kb

input:

36
bqsaqunccgyiarpeaezrgxpbqsaqunccgyiarpeaezrgxpbqsaqunccgyiarpeaezrgxpbqsaqunccgyiarpeaezrgxpbqsaqunccgyiarpeaezrgxpbqsaqunccgyiarpeaezrgxpbqsaqunccgyiarpeaezrgxpbqsaqunccgyiarpeaezrgxpbqsaqunccgyiarpeaezrgxpbqsaqunccgyiarpeaezrgxpbqsaqunccgyiarpeaezrgxpbqsaqunccgyiarpeaezrgxpbqsaqunccgyiarpeaezrg...

output:

49988
10658
28088
11977
49994
11321
13086
49974
12836
31204
11573
30769
29147
10648
12611
11999
49983
499970
13419
11724
19956
19953
29731
11345
12438
12680
19973
12970
19992
19986
36633
11087
10522
11308
10609
12006

result:

wrong answer 31st lines differ - expected: '30847', found: '36633'

Test #18:

score: 0
Wrong Answer
time: 127ms
memory: 152016kb

input:

36
ueuhiuuxbkqmcjrkbkknbuogliigucooglvofroicgveqoqtacgcwukjfuszwgpermvydlhfreljsdcuhkwdfgpmbhlznaefmbfrmmzdsmpmqrhxcddjmsvpziookuvyvbpjpqnideuvvbuzhxktrhkspahzvczsdpcvfrdkvxfszauizebrmljdlsfixedavhxbyalvyrpztjhsqkleljsdcuhkwdfgpfreljsdcuhkwdfgpmbhlznaefmbfrmmzdsmpmqrhxcddjmsvpziookuvyvbpjpqnideuvvbu...

output:

11223
11643
12012
19963
12651
45175
14468
45087
33112
19974
19950
19997
49982
49993
13154
19962
277645
10927
49970
12457
29707
26432
11485
11694
19977
12699
13358
19973
10948
11629
29009
19964
27385
12772
11344
10920

result:

wrong answer 6th lines differ - expected: '31459', found: '45175'

Test #19:

score: 5
Accepted
time: 104ms
memory: 110472kb

input:

400001
ggg
eee
hhh
ppp
eee
nnn
hhh
aaa
nnn
uuu
xxx
ddd
ttt
sss
jjj
fff
ccc
ddd
aaa
xxx
vvv
mmm
qqq
bbb
qqq
uuu
bbb
ggg
mmm
qqq
ccc
hhh
nnn
yyy
hhh
qqq
fff
www
xxx
uuu
iii
ggg
nnn
rrr
sss
aaa
eee
vvv
iii
eee
vvv
www
qqq
ddd
qqq
rrr
qqq
xxx
ppp
yyy
nnn
bbb
uuu
bbb
yyy
aaa
ttt
www
mmm
lll
qqq
ggg
zzz
b...

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 400001 lines

Test #20:

score: 5
Accepted
time: 171ms
memory: 152552kb

input:

27
xtahmwzugvrelqyihbryeggyvqgliwxirxrdvtxbopgahekrhbpnixmfpuryqqiipznksnljetllzvehwvugsimiffivvsfktvumihxmdixcdelbziiuquevzotugagzvcndjkposprxtczumhoddsacivyowgqridxtqmikdbiyfhtsqhxtczxkvxbtfrknwjiowszbthabqtticsbgratmzufenstlbbczubdpkdqcylkcdnjvnejoarsplnaoocqkftcpwstwgdyjqhgfnstnjncuafkrhadptfgra...

output:

12118
12260
19991
11406
13637
19972
19986
11246
12946
19984
11974
12449
12283
12022
12063
300783
11398
10957
11564
280619
12088
19972
11514
11971
11448
11649
12875

result:

ok 27 lines