QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#224729#3844. LCS Spanning TreeC1942huangjiaxuAC ✓1503ms680852kbC++141.4kb2023-10-23 12:12:592023-10-23 12:13:00

Judging History

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

  • [2023-10-23 12:13:00]
  • 评测
  • 测评结果:AC
  • 用时:1503ms
  • 内存:680852kb
  • [2023-10-23 12:12:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=4e6+5;
struct node{
	int fa,ch[26],ln;
}tr[N];
int cnt=1,ls,n,id[N],pa[N];
long long ans;
char s[N];
vector<int>e[N];
bool cmp(int x,int y){
	return tr[x].ln>tr[y].ln;
}
int ins(int c){
	int p=ls;
	if(tr[p].ch[c]){
		int q=tr[p].ch[c];
		if(tr[q].ln==tr[p].ln+1)return q;
		int nq=++cnt;tr[nq]=tr[q];
		tr[nq].ln=tr[p].ln+1,tr[q].fa=nq;
		for(;p&&tr[p].ch[c]==q;p=tr[p].fa)tr[p].ch[c]=nq;
		return nq;
	}
	int np=++cnt;
	tr[np].ln=tr[p].ln+1;
	for(;p&&!tr[p].ch[c];p=tr[p].fa)tr[p].ch[c]=np;
	if(!p)tr[np].fa=1;
	else{
		int q=tr[p].ch[c];
		if(tr[q].ln==tr[p].ln+1)tr[np].fa=q;
		else{
			int nq=++cnt;tr[nq]=tr[q];
			tr[nq].ln=tr[p].ln+1,tr[np].fa=tr[q].fa=nq;
			for(;p&&tr[p].ch[c]==q;p=tr[p].fa)tr[p].ch[c]=nq;
		}
	}
	return np;
}
int gp(int x){
	return pa[x]==x?pa[x]:pa[x]=gp(pa[x]);
}
void add(int x){
	scanf("%s",s+1),ls=1;
	int l=strlen(s+1);
	for(int i=1;i<=l;++i)ls=ins(s[i]-'a'),e[ls].push_back(x);
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)add(i),pa[i]=i;
	for(int i=1;i<=cnt;++i)id[i]=i;
	sort(id+1,id+cnt+1,cmp);
	for(int i=1,x;i<=cnt;++i){
		x=id[i];
		if(e[x].empty())continue;
		int u=gp(e[x][0]);
		for(auto v:e[x])if(gp(v)!=u){
			ans+=tr[x].ln;
			pa[gp(v)]=u;
		}
		e[tr[x].fa].push_back(u);
	}
	printf("%lld\n",ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 8ms
memory: 103844kb

input:

4
icpc
macau
regional
contest

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 19ms
memory: 105212kb

input:

3
ababa
babab
aba

output:

7

result:

ok single line: '7'

Test #3:

score: 0
Accepted
time: 616ms
memory: 391096kb

input:

26
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 15ms
memory: 105480kb

input:

7
jia
ran
jin
tian
chi
shen
me

output:

9

result:

ok single line: '9'

Test #5:

score: 0
Accepted
time: 8ms
memory: 103856kb

input:

10
theysaynothinglastsforever
weareonlyheretoday
loveisnowornever
bringmefaraway
takemetoyourheart
takemetoyoursoul
givemeyourhandandholdme
showmewhatloveis
bemyguidingstar
itiseasytakemetoyourheart

output:

55

result:

ok single line: '55'

Test #6:

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

input:

100
dblkekaekijliimalcaidjjfaghdmhifkiebieffbddjmflkhagajcfmkccjjadgiijdbdldgbbhgcfdcadbeiabkemiefdccmhdcfilhkfabmfdmigfgigdcibgaeicedfiidgecbhdamiaiefbmbgbjhklbhafmhckklbmmiemkcbfgjihmdjkai
bciiecmbc
cdjailkkbefkbmlekiefdhklcbdccfbgkagflfemjjmkjmcgiibldlmhbcldjajgafmakfbhecgcckkkglklljhmliehidbkicm...

output:

476

result:

ok single line: '476'

Test #7:

score: 0
Accepted
time: 1148ms
memory: 518176kb

input:

2000
ecbhcebgbcjgjiihdefajfbbaajfjdedggciaegdiijhijgedbgejhgjjfhabdfhbihdeegcehbcjhgebcjachbdeiefejefhcjdihfcfgeegdahhjhjiiffjjadifiijjbhhjjeffabiaagcjhaachjbiecfeceefddecjchjfibgedfdghgdijdcdahfeddjihbhbbghjjffdcibaggiiadbaajhfcgdbaafbicahjhabfdbeacccfdehebciafaaffdfjdciafbhidbahdccjhjdadcciecfbhac...

output:

17765

result:

ok single line: '17765'

Test #8:

score: 0
Accepted
time: 1028ms
memory: 502108kb

input:

1413
gjjmlceglbmbibjmmfcfmickcllfekgmicmifdbfgdgbeecgjgalbfkdfljjkclfgkaacdgigblaiaiehkeiccbjamikdgcjfemhhfebicddelklibjafmjhleebkimeblljfembgcgacdlkhjmbijjgacjaajebjfkcllffalheefeaedbmmkicaeecckdmedddbikeieimjmmcfdcgamicfbeimkjfamidjfhejdgiehkjkbdaaaeieldfibkkcgallieiamfehcdggiigkabblgigjgdlmflmafj...

output:

11429

result:

ok single line: '11429'

Test #9:

score: 0
Accepted
time: 80ms
memory: 119688kb

input:

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

output:

1999974

result:

ok single line: '1999974'

Test #10:

score: 0
Accepted
time: 1053ms
memory: 486896kb

input:

2
adwkgmoosmodblpylbpymmnbzyjzddfegdqppefjstpueeurhjpuvdxudgtgmaksfdjwhogcivwmbqeiavcxybubknkwqwqxzaujoclyzhnaztibonzpotsaicwaznyapujfwugvdtxfmhgcuhrlcklnminnxnoojzvfwbczubgijnldwcqzocodmdqltgzcguicwmdsombxbmcxotyfvmijsaulhtnppxtnkygakhzltbjjwjqrwyaozwzgroxhmquyocazjzkecvqzfgqdhttgpuojilqwbmurruscvd...

output:

8

result:

ok single line: '8'

Test #11:

score: 0
Accepted
time: 1503ms
memory: 670136kb

input:

1413
ababaaaababbababbabbaababaabaaaabaabbabababbbabbaaababbbbabbababaaababbbaabbaaabaaabababbbbbbbabbaababbababaaabaabbaaaaabbbaaabbabaaabaabaababaaabbabbabaabaabbaabbbbbbabbabaaaabbababaabbababbbaaabababaabaababaaaabaaaaababbbbbbbbabbabaabbaabbbbabbbbbaaabbbbbaabbbaabababababaaabbaaaaabbaaaabaaaaa...

output:

42405

result:

ok single line: '42405'

Test #12:

score: 0
Accepted
time: 24ms
memory: 115812kb

input:

1413
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

1995156

result:

ok single line: '1995156'

Test #13:

score: 0
Accepted
time: 1409ms
memory: 679388kb

input:

1
baababbbbbaaabbaabbabaabbabaababaabaaabbbbbbbabbbababbbabaaababbbabbabaaabbbbbaabbaabbaabaaabaaaabbbabbbaaabbbbbabbbaaabaabbabbbbaabbbabbbababaaabaababaabbbababbabbbbaaabbaabbbbbbabbabaaaabaaaabbbaaabbbbbbaaabaaabbabbababbabaabbabababababbbbaaababaaaabaabaaababbbbbabbbaaaaaababbbbbababaabbbabaaaab...

output:

0

result:

ok single line: '0'

Test #14:

score: 0
Accepted
time: 1027ms
memory: 525820kb

input:

1413
fnjfbnhskrerdxmxrlthhclkgcfrwukmccsfpbazsetxbfwvsseauqmcuutqofeshwxyxxasbtpfaocsgguayjcsdxitcnllliljglbjesqggubmbvozessjpcctrngdwsoedrpkjgsqatedrtfvlzhddjyvxfavxozcfooowhgzalctgjrriywmhvjeajzzxadepsslbbkdmpxsaoljmixvdgafpbgocjstdmegnrkbijvizjtnrqiwykdpmjfquxjympeziqdsbydahwpapyypkbfwmkohkxfwplv...

output:

464827

result:

ok single line: '464827'

Test #15:

score: 0
Accepted
time: 1030ms
memory: 507376kb

input:

1413
vrotfwuoloxhchhuitgryunhjurviyookrumnoabeziigrdpmlglfvurrlmblapvtlkhbmkgmuosltjxerkkmfdfspgeqwbjhlslycrkwhehdohhhrtuwwbpmivegwppikaimtulbyugobnwvjsrhtivddzjcrbmbbupvoayoxefatdvexnmqxhwdjhfairbmlsjbvjrspwsibonydbrcinfrwkrfduropcrkljeahyijoxhryaujnzakmurpqkgfmxpxivzsuhbihkchnwsaxtmlpfbfphldgccrab...

output:

254582

result:

ok single line: '254582'

Test #16:

score: 0
Accepted
time: 1152ms
memory: 631012kb

input:

1413
bbbbbabaabbabbbbbbaaabbaabaaabaabbabbaabaaabbbaaaaaabbaaabaaaabbabbbbbbbabbbbbabaaabaababbbaaabababbaaaaabbbbbabaaaabaaabbabbabbabaabaabaaabbbabbabaaababbbbbbaaaaababbabbbaabaaabaabbabbaaabaababaaabbbbabbabbabaaabbbabbbabbbbabaabbbabbbbabbbbaaabbbabaaabbaaaaabbababbababbbbbbaaaabaaaabaaaaabbabb...

output:

1498740

result:

ok single line: '1498740'

Test #17:

score: 0
Accepted
time: 814ms
memory: 480956kb

input:

1413
lcoqmejczgztniltuwtqgzmgyjdvkiqvlgozlzdmhchwksqerjuxkigjslgetycefqfqriezkmvwgndxyzvjiducocihbkogctyuecvqqqnxgsuerrpbwldkooupyixbdvxjzsaskppqhlvafmcbyfmmtgduqaxvxwfwohoawftfrofwahxyplmktpglrfjobolpxbsvhlaabhydrxeijqueibqzgzoipbzmctjlelnfsllllptufqaptqpzrdjgeluigdwlolsjzdwkusgcigrbzgcqlozpbvahzys...

output:

1285703

result:

ok single line: '1285703'

Test #18:

score: 0
Accepted
time: 988ms
memory: 496092kb

input:

500
eqrouzrzqavpwipjhbpbbsypakjkmpithzhdazdqzyivgzhpawsdorsrdcdstllansenrjgsjqqspxhrvaumtnfwrioktzmiusynbegluwdlvmcsoyghlleetuopwdzqxxdzdlmzjrkgdozunhbythfoetdaydswcxxgllfucsbhgcbtjduemztquysvdkrikqovbvpdnsmuwopitjmhkhyfiqaldtvnjjikhzpwubsqriymtnueuulcmnqrglepxobgqqcktvaldbzwovcirnneafvisczpsavisauo...

output:

93437

result:

ok single line: '93437'

Test #19:

score: 0
Accepted
time: 1472ms
memory: 674524kb

input:

500
aababbabbbabbbaabbaaababaabbabbaaaabbaaababababbbbbbbaabaaaabaabaabaababaabbaaabaaabaaaaabaababbaabaaabaaabababbabaabaaabaaaabaaabaabbabbbbababbbbbbabbbbbabaababbabaaaaaaabaabababbaabbbbbbbaaaaababaababaabbaaabaabbbaaaabbabbabbbbaabbbbaaaaabaabbabbababbaaababaaabbbabbabaaaabbaabbababbbbabbabbbaa...

output:

621482

result:

ok single line: '621482'

Test #20:

score: 0
Accepted
time: 834ms
memory: 495668kb

input:

500
xkhhkzemvoilwwysloxrngtnalowphqotywezcsuqahpwhjjwjalpvysipqxyhoshkyioqchqlyothxrqacivacersdqbrkkdisuywdqibgdidwbfylbanhsfmkjgutlemfeiiusjaxuftvltgoutxoajajpwfbatiedtawcavwhptsizieufsxpuigqnjqguwknwirydqgujadlljfqeehynopazfhtetgabazgqhbzjgkupsltwusjijmkqtduomvpmwvcfydoeoluiypesjqbscnjxqdleacsyzwd...

output:

1305055

result:

ok single line: '1305055'

Test #21:

score: 0
Accepted
time: 830ms
memory: 493604kb

input:

500
afdppltdvwipholvfwehnlbcmcxujuxlbabqnwtiudzbunzzjfiwqjzclyzwswiuylmmjiwdlygflfhumrtcbuhosgnmexieivsrdpuopcwckdywwrzxliofqdswacaixtbckxtzzpbjubgqthqgrgmhjgdjidtiyukitdhuukeqmmhhvzpmfbvqjazsfuceqomjuwdoijhwvodqptewwzmgznafhejxsvimtldcvkasagjpbnnzpbhoohtxnewgceuvrxzojahjgsajhniwoqlezgbnlzvndpixpkly...

output:

1248710

result:

ok single line: '1248710'

Test #22:

score: 0
Accepted
time: 1080ms
memory: 522580kb

input:

4000
gdlglqbydbkucqucvkhjoicbrutfyulgywmlpqlurxpvqhkywpnnwerqgjnnxyheruhcotfjpohhyrfwiulgbcyjnnwlofrfcykqspchfjqfcyemupuvutghifuykmeokohcfjlmueuycykwpeujzctkhpibmfvorjdmqztnqyqzjgzcsekanoxzescqxxeojjczivoywhzhpzjhftkvjhunzwfzwlphvsifpweldfstgdcoymjktfzvdfubqlilfqrvpxiuednlgqzhekrypstuxpwqagbgzubotli...

output:

587656

result:

ok single line: '587656'

Test #23:

score: 0
Accepted
time: 1154ms
memory: 597352kb

input:

4000
baabaabbababbbbbabaabaabababaabaabbbabbaaaabbbabbaaababbbaaaabaababbbbbbbbaaaaabbabaabbabbabaabbaaabbbaaaabbbbaabaabbbbaabbaaaaaaaaaaaaabbbaaaabaabbbabbaabaabaaaaaabbaaaaabaaaaabbbaaaaabaabaaaaaaabbaabbaaabbaabaabbabbbaaaaaaabbbabbbabbaaabaababbaaabbaabbababaabbbbaaaaabbaabbbaaabbabababbbbbaaaa...

output:

867646

result:

ok single line: '867646'

Test #24:

score: 0
Accepted
time: 1204ms
memory: 598720kb

input:

4000
baaaabbabbaaaabbbaaabbababaaaababbbaaabbbbbbbaabaabbbbbbbbbbbabbaabaabbbaabaabbaaaababbbaaabbbabaababaababbaaaaabaabbbabbababbbbbaaaaaaabbabababbaabbaaaabbbbababbbbbbaaaababbbbbbaababbaabbaabbbababbaabbabbaaababababaaababbbaaabbaababbbbbaaaabababaabbabaabaaaaabbaaaabbababaaaaaaababaabbbbabbbabb...

output:

870160

result:

ok single line: '870160'

Test #25:

score: 0
Accepted
time: 736ms
memory: 468844kb

input:

4000
jnbnjwgrxbxyqkbxyktdciatkisupcgkaanotwsywpwnczkakgfmohiypavecbrddgrwemuadsphrchdioswvaxnastcvmhasbwynsbsmqafsjjcybzvbwidqchnqpnjqjjfdkzpbzuvldyjgzejxpmntuajlpufrlzkaisoonwikhonlrvvrqszrenfgtmyeokhwcxkrwtbdjqqalltddvvhicqbroifyrbcootmjwrsmhuxspdykahscxwtnganxepnskabgrvuzrutgxttxdlbajvqpvdmbtatfc...

output:

913862

result:

ok single line: '913862'

Test #26:

score: 0
Accepted
time: 32ms
memory: 116996kb

input:

4000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

1979531

result:

ok single line: '1979531'

Test #27:

score: 0
Accepted
time: 838ms
memory: 497520kb

input:

4000
fdhdijdfcdeedcbjgafdgcdegdbibaahdhaeifbdafhfhaefacigedcdhfbifdhbcjhaeidhdccdchicbjafceabjdchgjaabhbffgcajhdbecghdiehffjgiddhcfhdcabhhfigcdjihffagaibhjhhcdegiecbedabaajdgjbefbdbadcdeefgbibbhgaedhbhjgejchfjiididfcibjefhfgebiagfdfejjgbhdcfefghdafgjbbijaeciebghgcgiijhedeijahecfabgcbhefacbbaijdghdhe...

output:

1228665

result:

ok single line: '1228665'

Test #28:

score: 0
Accepted
time: 790ms
memory: 477404kb

input:

4000
rjdknocpagvrnghrpyukwifkkddprokianvndxdwgczcauhwrkpqmhqsmxqpmoxhazmujpspurtwndsfphxcrnwfnmuzauictvwfmowghscvvwckgzoxnkcawybzukbohyvtmrcwjgrgdvzovoosphzmirifzwmbfzuauwkmgoaodbfasvtjcuxmnftmcfohhkhdgtppkrfnvmpnhiwletasztebbskidtnjocaywgnrsdecnapsvpkuloxojjymelxtpyrlgfcakiexkurglbcwscmblkpqvmjlmcw...

output:

911422

result:

ok single line: '911422'

Test #29:

score: 0
Accepted
time: 521ms
memory: 335428kb

input:

100000
tduxfndk
uneyosepeblysz
myyzqqfxlyol
hueyo
vxkovfhrybgmvlhweq
jkcclhdeyo
dyggb
mokfduurtqfsmaeynq
gluuajukjnjc
dfcjqnme
xyrupyxgfnwd
hvdjjbewg
jjeyjmmlyol
fiqebs
otpjpq
nfmezyyuyme
wxyiuymslehvl
coshvqaht
tftlwgbnjyicrvjmuwrx
owpmmwkqpvhwxhiujh
vxrvymrouzryawtwombk
ukkzjbon
gokkrpnzmhonmhkfpj...

output:

989636

result:

ok single line: '989636'

Test #30:

score: 0
Accepted
time: 531ms
memory: 324892kb

input:

100000
baaabbbbabbabaaaba
baabbaababbababbb
bbbbbaababab
baaabbaa
abbabbbb
baaabba
baaabbbbbab
bababbabbbb
aababbbbbaabbbbabbbb
abaababbaaaaabbb
abaaabaaabbbbabbb
bababaababbb
aababbabbbbbbababba
abaabbabab
abbabbaaabaaaabbaaba
abbaaabbaabbbba
bbaababbabbaaabaaaa
aaababaaabbbabb
babbbb
bbbbaaaabaabb...

output:

1282986

result:

ok single line: '1282986'

Test #31:

score: 0
Accepted
time: 415ms
memory: 297672kb

input:

100000
pkhvbtnxfvxaem
uxvbtnxcgcsmwurthw
rfvxaem
wgzfvxaem
fafvxaem
nghhlpjfdga
wcljhoesadwmfwhvbtnx
uvbtnx
bcbffvxaemvbtnx
jhoesadwmfwhvbtnx
ncgcsmwurthwvbtnx
kyvbtnxjhoesadwmfwh
wavbtnxjhoesadwmfwh
ivbtnxssu
qnghhlpjfdgarjw
vbtnxibjhoesadwmfwh
zfvxaemigqvbtnx
swcgcsmwurthwsc
sjhoesadwmfwh
dfvxaemp...

output:

1170625

result:

ok single line: '1170625'

Test #32:

score: 0
Accepted
time: 37ms
memory: 120440kb

input:

100000
aaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaa
aaaaa
aaaaa
aaaaaaaaa
aaaaaaaaaaa
aaaaaaaaaaaaaaaa
aaaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaaaaa
aaaaaa
aaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaa
aaaaaaaa
aaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaa
aaaaaaaaaaa
aaaaaaaaaaaaaa
aaaaa
aaaaaaaaa
aaaaaaaaaaaaaaa
aaaaaaaaaaaaa
...

output:

1950179

result:

ok single line: '1950179'

Test #33:

score: 0
Accepted
time: 916ms
memory: 520332kb

input:

20
cqhcbnnuobmgcqfdzbuvyajaidogyrtcjbemouifxulzlqcmtwiryttiwhpuykxjldvaxefuastnkvaeukxsdtdcauwbevkqziswmzrmrmabkchemhyrabtavqdajwzphqhuggbrujigzfhqxcrtcifvvvfgrevavfwdlauhjenkjudgyubcfhxcccivjfyemujywfhfjxsutvcsreuwnuypwimfqmlcjucfzklkhdeaahurnrqalqrjzfrrsctbzygaktltyrvyyqsnjinwyghzmyqgdmhekpeulrnjj...

output:

201946

result:

ok single line: '201946'

Test #34:

score: 0
Accepted
time: 1390ms
memory: 679348kb

input:

20
baaababababababbaaaabababaaaabbabbaaabbbaabbaabaabbbabaabbbabbaabbbbabaaaabaabaabbbbaaaabbaaaaabaaaabaabbbbbbaaabbbabbaaaababbbbbbbaabbbababbabaababaaabbbbaabbaaaaababbbabaaaaabbaabababaabbbbabaaaaaababbabbbbabbabaaaabbaabaabaabaaaabbbbaaabbbbabbababbbabbbabaaaabbbaaaaabbbababbaaabbbbaabbbbbbabba...

output:

187803

result:

ok single line: '187803'

Test #35:

score: 0
Accepted
time: 828ms
memory: 497716kb

input:

20
wighspqotssudabkedkygymrryunfudbdlkxbdnwxfqbitnmwxmeyyypysfgoihtuuqxxgtullvvgjhcivigwiyucdatnkmhefgblbxymtusedwozhxxrvruaunngbxkifnvhkwvfqolvmawvxtnunjuhwjnzizioofvabqgtgtpvtnqshfmwoidmssmatwohblhdepwmjnhcbavkfjgwslikfumysdfwombscxfnnopqomcwyksqvaaaxoaprflgtmaxmfkbwcrkqtgodaeabgcyvepmjduervefcqgy...

output:

265680

result:

ok single line: '265680'

Test #36:

score: 0
Accepted
time: 47ms
memory: 146516kb

input:

20
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

1799368

result:

ok single line: '1799368'

Test #37:

score: 0
Accepted
time: 1365ms
memory: 680852kb

input:

2
aabaaabababbaababaaabaaaaababaabaabaabaabbbbbbaabaaabaabaabaabbbbbbaaaabbbabaabbbabaaabbaabababbbbbbbbaaabbbbbaabaababaabbabaaabbbbaabaaaababaaaabbaaaaababbabbbaababaaaaaabaababaaaaaaaabbbaaaaaaaaaaaaaabaaaaaaaabaabbbaabbabbabbabbaabbaabbaababaaabbababbbbaaaababbbaababbaabbabbbabaababaabaababaaaab...

output:

92934

result:

ok single line: '92934'

Test #38:

score: 0
Accepted
time: 906ms
memory: 500368kb

input:

2
jcmgevxqwiaflstvldrnmkeoeczrruqbxfjdagtyptfcoyybepqqzvggxgxpcpsbubfxhyvyubbkbznfqdysyeywmxlrodslgxipyfougrgkstriwpavwatkzgbolwbrtjgtownxnthfoyqlqsimvbwuhakuwllrurllqakdwtlkrdvjvfvqiunruxlslwjhqwsgzcjvvwfpzdyxkwntqakmawglurskonqnpcknarecwezhaoasrmgrkmefgwpujijbmvqomwqjarsbguvxgcqrqwwwsnsexdhjazanvq...

output:

91737

result:

ok single line: '91737'

Test #39:

score: 0
Accepted
time: 236ms
memory: 384192kb

input:

2
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

93662

result:

ok single line: '93662'

Test #40:

score: 0
Accepted
time: 993ms
memory: 526264kb

input:

10
cdvthwmepkhrkkvpucesqgrdwtzdvicynxrutfykridcsbrpfvhwdabzucdpkhpxhgtcospfashuvajdxqzarcclefcrosqvakyoenughdadgmgdchgvjiinpleddvbfhzuloqtvvtabfihkpnfaxqqmburgrslathljxehvahwhsftjszkpradswxaqrlqlvewukdpmlouftnomoydfajzzgzpxnhkilhcykskxiecburpkrtsuctvktkhitsqhzuflopjwwnysgneaiwumqpwlbetwwldxfiiuatqwh...

output:

735652

result:

ok single line: '735652'

Test #41:

score: 0
Accepted
time: 994ms
memory: 508936kb

input:

4000
fcrfjdagkknhhvvklrmnnnqcrmjnifrphkwsnyaxiqfpnczytnngbejusuhabapjkodzmgwvydmlfomabzhedsywmhyohqzreeqqmpnkuawcoicrhlwndwjsehilzjfdnxwcmjmjjklzsptcbrpenaytjgfjpmmfjihyuvhfguhyjacktrrgrpadyhmptaueldcfzjkfdrfptizmbqvvixyiekxzmudxxgcwrpdxilmcvnqweltokrwqdtpsnvpndulujpttchxxvotzbppmilcmguewpvjupuoalku...

output:

555122

result:

ok single line: '555122'

Test #42:

score: 0
Accepted
time: 1362ms
memory: 657852kb

input:

4000
abbaaabaabbabbbbaaaaaabaaaaaaababbabbaaabbaaabbabaaaababaabaaaabbbbbbbbaabaaaaaaaaaababbaababababababaabbabaabaababbaaaabaaaababaabbabbabaaaaaababaaababbabbbbabbbbaaaabaabaaaaabaabbaaaabbbbbbaaaaaaaaaabbabbabbaababbaababababbabbbbbbbaaababbbaabbbabaabbbbaabbbabaaabaaaaabbabbbbbabbbaaaaaaababbab...

output:

777185

result:

ok single line: '777185'

Test #43:

score: 0
Accepted
time: 1453ms
memory: 680768kb

input:

2
baaaaaaabaaabaaaaabbaababbabbababbabbaabaabbbbbbbbabbbabaaabaabbbbbbabaabbaaabbbabaaaabbababbaabbbabaaaabaabbaaabaaabbbbabaabbbbababbabaabbabbabbababaabbabbbaaabababaabbbbbabaabbaabaaabbbaababababbaabaaaabaabbbbabbaababbbbabbaaabbbbbbbabababbaaabbbbaaabbaababababaabbbbaaabaaabbbababbbbbababbbabbba...

output:

54

result:

ok single line: '54'