QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#698690#3844. LCS Spanning Treeyzj123AC ✓1123ms805284kbC++202.7kb2024-11-01 21:22:372024-11-01 21:22:39

Judging History

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

  • [2024-11-01 21:22:39]
  • 评测
  • 测评结果:AC
  • 用时:1123ms
  • 内存:805284kb
  • [2024-11-01 21:22:37]
  • 提交

answer

#include <bits/stdc++.h>
#define Re register int
#define LL long long
using namespace std;
const int MAXN=4e6+5;
int n;
char ch[MAXN];
struct extended_SAM {
	int tot;
	int link[MAXN], maxlen[MAXN];
	int ch[MAXN][26];
	//link[i]: 后缀链接
	//ch[i]: 状态转移数组
	extended_SAM() {
		tot = 1;
	}//根初始化为1
	int insert(int x, int last) 
	{
		if(ch[last][x]) 
		{
			int p = last, np = ch[p][x];
			if(maxlen[p] + 1 == maxlen[np]) return np; //即最初的特判1
			else 
			{
				int q = ++tot;
				maxlen[q] = maxlen[p] + 1;
				for (int i = 0; i < 26; i++) ch[q][i] = ch[np][i];
				while (p && ch[p][x] == np) ch[p][x] = q, p = link[p];
				link[q] = link[np];
				link[np] = q;
				return q;//即最初的特判2
			}
		}
		int p = last, np = ++tot;
		maxlen[np] = maxlen[last] + 1;
		while(p && !ch[p][x]) ch[p][x] = np, p = link[p];
		if(!p) link[np] = 1;
		else 
		{
			int q = ch[p][x];
			if(maxlen[p] + 1 == maxlen[q]) link[np] = q;
			else 
			{
				int nq = ++tot;
				maxlen[nq] = maxlen[p] + 1;
				for (int i = 0; i < 26; i++) ch[nq][i] = ch[q][i];
				while(p && ch[p][x] == q) ch[p][x] = nq, p=link[p];
				link[nq] = link[q];
				link[np] = link[q]= nq;
			}
		}
		return np;
	}
} SAM;
vector<int> g[MAXN], col[MAXN];
int prt[MAXN];
pair<int, int> a[MAXN];
int get_prt(int x) {
    if (x == prt[x]) return x;
    return prt[x] = get_prt(prt[x]);
}
int cr[MAXN];
int ans;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) prt[i] = i;
    for(Re i=1;i<=n;++i){
        scanf("%s",ch+1);
        Re last=1;
        for(Re j=1;ch[j];++j)
        {
            last=SAM.insert(ch[j]-'a',last);
            col[last].push_back(i);
        }
    }
    for (int i = 1; i <= SAM.tot; i++) g[SAM.link[i]].push_back(i);
    for (int i = 1; i <= SAM.tot; i++) a[i] = make_pair(SAM.maxlen[i], i);
    sort(a + 1, a + SAM.tot + 1, [](pair<int, int> A, pair<int, int> B){
        return A.first > B.first;
    });
    vector<int> vex;
    int k = 0;
    for (int i = 1; i <= SAM.tot; i++) 
    {
        vex.clear();
        int u = a[i].second, val = a[i].first;
        for (int x : col[u]) vex.push_back(x);
        for (int x : g[u]) vex.push_back(cr[x]);
        for (int j = 1; j < vex.size(); j++)
        {
            int x = vex[j], y = vex[j - 1];
            int prtx = get_prt(x), prty = get_prt(y);
            if (prtx != prty) 
            {
                prt[prtx] = prty;
                ans += val;
                k++;
            }
        }
        if (vex.size() > 0) cr[u] = get_prt(vex[0]);
    }
    cout << ans;
    return 0;
}
/*
4
icpc
macau
regional 
contest

3
ababa 
babab 
aba
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 9ms
memory: 11904kb

input:

4
icpc
macau
regional
contest

output:

4

result:

ok single line: '4'

Test #2:

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

input:

3
ababa
babab
aba

output:

7

result:

ok single line: '7'

Test #3:

score: 0
Accepted
time: 288ms
memory: 473192kb

input:

26
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

0

result:

ok single line: '0'

Test #4:

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

input:

7
jia
ran
jin
tian
chi
shen
me

output:

9

result:

ok single line: '9'

Test #5:

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

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: 9ms
memory: 14176kb

input:

100
dblkekaekijliimalcaidjjfaghdmhifkiebieffbddjmflkhagajcfmkccjjadgiijdbdldgbbhgcfdcadbeiabkemiefdccmhdcfilhkfabmfdmigfgigdcibgaeicedfiidgecbhdamiaiefbmbgbjhklbhafmhckklbmmiemkcbfgjihmdjkai
bciiecmbc
cdjailkkbefkbmlekiefdhklcbdccfbgkagflfemjjmkjmcgiibldlmhbcldjajgafmakfbhecgcckkkglklljhmliehidbkicm...

output:

476

result:

ok single line: '476'

Test #7:

score: 0
Accepted
time: 968ms
memory: 586428kb

input:

2000
ecbhcebgbcjgjiihdefajfbbaajfjdedggciaegdiijhijgedbgejhgjjfhabdfhbihdeegcehbcjhgebcjachbdeiefejefhcjdihfcfgeegdahhjhjiiffjjadifiijjbhhjjeffabiaagcjhaachjbiecfeceefddecjchjfibgedfdghgdijdcdahfeddjihbhbbghjjffdcibaggiiadbaajhfcgdbaafbicahjhabfdbeacccfdehebciafaaffdfjdciafbhidbahdccjhjdadcciecfbhac...

output:

17765

result:

ok single line: '17765'

Test #8:

score: 0
Accepted
time: 885ms
memory: 557892kb

input:

1413
gjjmlceglbmbibjmmfcfmickcllfekgmicmifdbfgdgbeecgjgalbfkdfljjkclfgkaacdgigblaiaiehkeiccbjamikdgcjfemhhfebicddelklibjafmjhleebkimeblljfembgcgacdlkhjmbijjgacjaajebjfkcllffalheefeaedbmmkicaeecckdmedddbikeieimjmmcfdcgamicfbeimkjfamidjfhejdgiehkjkbdaaaeieldfibkkcgallieiamfehcdggiigkabblgigjgdlmflmafj...

output:

11429

result:

ok single line: '11429'

Test #9:

score: 0
Accepted
time: 89ms
memory: 28680kb

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: 789ms
memory: 538908kb

input:

2
adwkgmoosmodblpylbpymmnbzyjzddfegdqppefjstpueeurhjpuvdxudgtgmaksfdjwhogcivwmbqeiavcxybubknkwqwqxzaujoclyzhnaztibonzpotsaicwaznyapujfwugvdtxfmhgcuhrlcklnminnxnoojzvfwbczubgijnldwcqzocodmdqltgzcguicwmdsombxbmcxotyfvmijsaulhtnppxtnkygakhzltbjjwjqrwyaozwzgroxhmquyocazjzkecvqzfgqdhttgpuojilqwbmurruscvd...

output:

8

result:

ok single line: '8'

Test #11:

score: 0
Accepted
time: 1106ms
memory: 795692kb

input:

1413
ababaaaababbababbabbaababaabaaaabaabbabababbbabbaaababbbbabbababaaababbbaabbaaabaaabababbbbbbbabbaababbababaaabaabbaaaaabbbaaabbabaaabaabaababaaabbabbabaabaabbaabbbbbbabbabaaaabbababaabbababbbaaabababaabaababaaaabaaaaababbbbbbbbabbabaabbaabbbbabbbbbaaabbbbbaabbbaabababababaaabbaaaaabbaaaabaaaaa...

output:

42405

result:

ok single line: '42405'

Test #12:

score: 0
Accepted
time: 25ms
memory: 23364kb

input:

1413
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

1995156

result:

ok single line: '1995156'

Test #13:

score: 0
Accepted
time: 1041ms
memory: 805112kb

input:

1
baababbbbbaaabbaabbabaabbabaababaabaaabbbbbbbabbbababbbabaaababbbabbabaaabbbbbaabbaabbaabaaabaaaabbbabbbaaabbbbbabbbaaabaabbabbbbaabbbabbbababaaabaababaabbbababbabbbbaaabbaabbbbbbabbabaaaabaaaabbbaaabbbbbbaaabaaabbabbababbabaabbabababababbbbaaababaaaabaabaaababbbbbabbbaaaaaababbbbbababaabbbabaaaab...

output:

0

result:

ok single line: '0'

Test #14:

score: 0
Accepted
time: 866ms
memory: 587268kb

input:

1413
fnjfbnhskrerdxmxrlthhclkgcfrwukmccsfpbazsetxbfwvsseauqmcuutqofeshwxyxxasbtpfaocsgguayjcsdxitcnllliljglbjesqggubmbvozessjpcctrngdwsoedrpkjgsqatedrtfvlzhddjyvxfavxozcfooowhgzalctgjrriywmhvjeajzzxadepsslbbkdmpxsaoljmixvdgafpbgocjstdmegnrkbijvizjtnrqiwykdpmjfquxjympeziqdsbydahwpapyypkbfwmkohkxfwplv...

output:

464827

result:

ok single line: '464827'

Test #15:

score: 0
Accepted
time: 910ms
memory: 565692kb

input:

1413
vrotfwuoloxhchhuitgryunhjurviyookrumnoabeziigrdpmlglfvurrlmblapvtlkhbmkgmuosltjxerkkmfdfspgeqwbjhlslycrkwhehdohhhrtuwwbpmivegwppikaimtulbyugobnwvjsrhtivddzjcrbmbbupvoayoxefatdvexnmqxhwdjhfairbmlsjbvjrspwsibonydbrcinfrwkrfduropcrkljeahyijoxhryaujnzakmurpqkgfmxpxivzsuhbihkchnwsaxtmlpfbfphldgccrab...

output:

254582

result:

ok single line: '254582'

Test #16:

score: 0
Accepted
time: 619ms
memory: 747352kb

input:

1413
bbbbbabaabbabbbbbbaaabbaabaaabaabbabbaabaaabbbaaaaaabbaaabaaaabbabbbbbbbabbbbbabaaabaababbbaaabababbaaaaabbbbbabaaaabaaabbabbabbabaabaabaaabbbabbabaaababbbbbbaaaaababbabbbaabaaabaabbabbaaabaababaaabbbbabbabbabaaabbbabbbabbbbabaabbbabbbbabbbbaaabbbabaaabbaaaaabbababbababbbbbbaaaabaaaabaaaaabbabb...

output:

1498740

result:

ok single line: '1498740'

Test #17:

score: 0
Accepted
time: 536ms
memory: 513588kb

input:

1413
lcoqmejczgztniltuwtqgzmgyjdvkiqvlgozlzdmhchwksqerjuxkigjslgetycefqfqriezkmvwgndxyzvjiducocihbkogctyuecvqqqnxgsuerrpbwldkooupyixbdvxjzsaskppqhlvafmcbyfmmtgduqaxvxwfwohoawftfrofwahxyplmktpglrfjobolpxbsvhlaabhydrxeijqueibqzgzoipbzmctjlelnfsllllptufqaptqpzrdjgeluigdwlolsjzdwkusgcigrbzgcqlozpbvahzys...

output:

1285703

result:

ok single line: '1285703'

Test #18:

score: 0
Accepted
time: 849ms
memory: 549948kb

input:

500
eqrouzrzqavpwipjhbpbbsypakjkmpithzhdazdqzyivgzhpawsdorsrdcdstllansenrjgsjqqspxhrvaumtnfwrioktzmiusynbegluwdlvmcsoyghlleetuopwdzqxxdzdlmzjrkgdozunhbythfoetdaydswcxxgllfucsbhgcbtjduemztquysvdkrikqovbvpdnsmuwopitjmhkhyfiqaldtvnjjikhzpwubsqriymtnueuulcmnqrglepxobgqqcktvaldbzwovcirnneafvisczpsavisauo...

output:

93437

result:

ok single line: '93437'

Test #19:

score: 0
Accepted
time: 1051ms
memory: 801608kb

input:

500
aababbabbbabbbaabbaaababaabbabbaaaabbaaababababbbbbbbaabaaaabaabaabaababaabbaaabaaabaaaaabaababbaabaaabaaabababbabaabaaabaaaabaaabaabbabbbbababbbbbbabbbbbabaababbabaaaaaaabaabababbaabbbbbbbaaaaababaababaabbaaabaabbbaaaabbabbabbbbaabbbbaaaaabaabbabbababbaaababaaabbbabbabaaaabbaabbababbbbabbabbbaa...

output:

621482

result:

ok single line: '621482'

Test #20:

score: 0
Accepted
time: 671ms
memory: 528828kb

input:

500
xkhhkzemvoilwwysloxrngtnalowphqotywezcsuqahpwhjjwjalpvysipqxyhoshkyioqchqlyothxrqacivacersdqbrkkdisuywdqibgdidwbfylbanhsfmkjgutlemfeiiusjaxuftvltgoutxoajajpwfbatiedtawcavwhptsizieufsxpuigqnjqguwknwirydqgujadlljfqeehynopazfhtetgabazgqhbzjgkupsltwusjijmkqtduomvpmwvcfydoeoluiypesjqbscnjxqdleacsyzwd...

output:

1305055

result:

ok single line: '1305055'

Test #21:

score: 0
Accepted
time: 504ms
memory: 524000kb

input:

500
afdppltdvwipholvfwehnlbcmcxujuxlbabqnwtiudzbunzzjfiwqjzclyzwswiuylmmjiwdlygflfhumrtcbuhosgnmexieivsrdpuopcwckdywwrzxliofqdswacaixtbckxtzzpbjubgqthqgrgmhjgdjidtiyukitdhuukeqmmhhvzpmfbvqjazsfuceqomjuwdoijhwvodqptewwzmgznafhejxsvimtldcvkasagjpbnnzpbhoohtxnewgceuvrxzojahjgsajhniwoqlezgbnlzvndpixpkly...

output:

1248710

result:

ok single line: '1248710'

Test #22:

score: 0
Accepted
time: 823ms
memory: 589508kb

input:

4000
gdlglqbydbkucqucvkhjoicbrutfyulgywmlpqlurxpvqhkywpnnwerqgjnnxyheruhcotfjpohhyrfwiulgbcyjnnwlofrfcykqspchfjqfcyemupuvutghifuykmeokohcfjlmueuycykwpeujzctkhpibmfvorjdmqztnqyqzjgzcsekanoxzescqxxeojjczivoywhzhpzjhftkvjhunzwfzwlphvsifpweldfstgdcoymjktfzvdfubqlilfqrvpxiuednlgqzhekrypstuxpwqagbgzubotli...

output:

587656

result:

ok single line: '587656'

Test #23:

score: 0
Accepted
time: 771ms
memory: 708320kb

input:

4000
baabaabbababbbbbabaabaabababaabaabbbabbaaaabbbabbaaababbbaaaabaababbbbbbbbaaaaabbabaabbabbabaabbaaabbbaaaabbbbaabaabbbbaabbaaaaaaaaaaaaabbbaaaabaabbbabbaabaabaaaaaabbaaaaabaaaaabbbaaaaabaabaaaaaaabbaabbaaabbaabaabbabbbaaaaaaabbbabbbabbaaabaababbaaabbaabbababaabbbbaaaaabbaabbbaaabbabababbbbbaaaa...

output:

867646

result:

ok single line: '867646'

Test #24:

score: 0
Accepted
time: 773ms
memory: 709008kb

input:

4000
baaaabbabbaaaabbbaaabbababaaaababbbaaabbbbbbbaabaabbbbbbbbbbbabbaabaabbbaabaabbaaaababbbaaabbbabaababaababbaaaaabaabbbabbababbbbbaaaaaaabbabababbaabbaaaabbbbababbbbbbaaaababbbbbbaababbaabbaabbbababbaabbabbaaababababaaababbbaaabbaababbbbbaaaabababaabbabaabaaaaabbaaaabbababaaaaaaababaabbbbabbbabb...

output:

870160

result:

ok single line: '870160'

Test #25:

score: 0
Accepted
time: 482ms
memory: 508300kb

input:

4000
jnbnjwgrxbxyqkbxyktdciatkisupcgkaanotwsywpwnczkakgfmohiypavecbrddgrwemuadsphrchdioswvaxnastcvmhasbwynsbsmqafsjjcybzvbwidqchnqpnjqjjfdkzpbzuvldyjgzejxpmntuajlpufrlzkaisoonwikhonlrvvrqszrenfgtmyeokhwcxkrwtbdjqqalltddvvhicqbroifyrbcootmjwrsmhuxspdykahscxwtnganxepnskabgrvuzrutgxttxdlbajvqpvdmbtatfc...

output:

913862

result:

ok single line: '913862'

Test #26:

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

input:

4000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

1979531

result:

ok single line: '1979531'

Test #27:

score: 0
Accepted
time: 578ms
memory: 547084kb

input:

4000
fdhdijdfcdeedcbjgafdgcdegdbibaahdhaeifbdafhfhaefacigedcdhfbifdhbcjhaeidhdccdchicbjafceabjdchgjaabhbffgcajhdbecghdiehffjgiddhcfhdcabhhfigcdjihffagaibhjhhcdegiecbedabaajdgjbefbdbadcdeefgbibbhgaedhbhjgejchfjiididfcibjefhfgebiagfdfejjgbhdcfefghdafgjbbijaeciebghgcgiijhedeijahecfabgcbhefacbbaijdghdhe...

output:

1228665

result:

ok single line: '1228665'

Test #28:

score: 0
Accepted
time: 591ms
memory: 518452kb

input:

4000
rjdknocpagvrnghrpyukwifkkddprokianvndxdwgczcauhwrkpqmhqsmxqpmoxhazmujpspurtwndsfphxcrnwfnmuzauictvwfmowghscvvwckgzoxnkcawybzukbohyvtmrcwjgrgdvzovoosphzmirifzwmbfzuauwkmgoaodbfasvtjcuxmnftmcfohhkhdgtppkrfnvmpnhiwletasztebbskidtnjocaywgnrsdecnapsvpkuloxojjymelxtpyrlgfcakiexkurglbcwscmblkpqvmjlmcw...

output:

911422

result:

ok single line: '911422'

Test #29:

score: 0
Accepted
time: 466ms
memory: 330636kb

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: 431ms
memory: 317288kb

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: 402ms
memory: 272568kb

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: 46ms
memory: 35164kb

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: 645ms
memory: 562680kb

input:

20
cqhcbnnuobmgcqfdzbuvyajaidogyrtcjbemouifxulzlqcmtwiryttiwhpuykxjldvaxefuastnkvaeukxsdtdcauwbevkqziswmzrmrmabkchemhyrabtavqdajwzphqhuggbrujigzfhqxcrtcifvvvfgrevavfwdlauhjenkjudgyubcfhxcccivjfyemujywfhfjxsutvcsreuwnuypwimfqmlcjucfzklkhdeaahurnrqalqrjzfrrsctbzygaktltyrvyyqsnjinwyghzmyqgdmhekpeulrnjj...

output:

201946

result:

ok single line: '201946'

Test #34:

score: 0
Accepted
time: 819ms
memory: 801420kb

input:

20
baaababababababbaaaabababaaaabbabbaaabbbaabbaabaabbbabaabbbabbaabbbbabaaaabaabaabbbbaaaabbaaaaabaaaabaabbbbbbaaabbbabbaaaababbbbbbbaabbbababbabaababaaabbbbaabbaaaaababbbabaaaaabbaabababaabbbbabaaaaaababbabbbbabbabaaaabbaabaabaabaaaabbbbaaabbbbabbababbbabbbabaaaabbbaaaaabbbababbaaabbbbaabbbbbbabba...

output:

187803

result:

ok single line: '187803'

Test #35:

score: 0
Accepted
time: 568ms
memory: 530516kb

input:

20
wighspqotssudabkedkygymrryunfudbdlkxbdnwxfqbitnmwxmeyyypysfgoihtuuqxxgtullvvgjhcivigwiyucdatnkmhefgblbxymtusedwozhxxrvruaunngbxkifnvhkwvfqolvmawvxtnunjuhwjnzizioofvabqgtgtpvtnqshfmwoidmssmatwohblhdepwmjnhcbavkfjgwslikfumysdfwombscxfnnopqomcwyksqvaaaxoaprflgtmaxmfkbwcrkqtgodaeabgcyvepmjduervefcqgy...

output:

265680

result:

ok single line: '265680'

Test #36:

score: 0
Accepted
time: 55ms
memory: 70020kb

input:

20
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

1799368

result:

ok single line: '1799368'

Test #37:

score: 0
Accepted
time: 1123ms
memory: 805284kb

input:

2
aabaaabababbaababaaabaaaaababaabaabaabaabbbbbbaabaaabaabaabaabbbbbbaaaabbbabaabbbabaaabbaabababbbbbbbbaaabbbbbaabaababaabbabaaabbbbaabaaaababaaaabbaaaaababbabbbaababaaaaaabaababaaaaaaaabbbaaaaaaaaaaaaaabaaaaaaaabaabbbaabbabbabbabbaabbaabbaababaaabbababbbbaaaababbbaababbaabbabbbabaababaabaababaaaab...

output:

92934

result:

ok single line: '92934'

Test #38:

score: 0
Accepted
time: 829ms
memory: 552692kb

input:

2
jcmgevxqwiaflstvldrnmkeoeczrruqbxfjdagtyptfcoyybepqqzvggxgxpcpsbubfxhyvyubbkbznfqdysyeywmxlrodslgxipyfougrgkstriwpavwatkzgbolwbrtjgtownxnthfoyqlqsimvbwuhakuwllrurllqakdwtlkrdvjvfvqiunruxlslwjhqwsgzcjvvwfpzdyxkwntqakmawglurskonqnpcknarecwezhaoasrmgrkmefgwpujijbmvqomwqjarsbguvxgcqrqwwwsnsexdhjazanvq...

output:

91737

result:

ok single line: '91737'

Test #39:

score: 0
Accepted
time: 179ms
memory: 455748kb

input:

2
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

93662

result:

ok single line: '93662'

Test #40:

score: 0
Accepted
time: 807ms
memory: 587152kb

input:

10
cdvthwmepkhrkkvpucesqgrdwtzdvicynxrutfykridcsbrpfvhwdabzucdpkhpxhgtcospfashuvajdxqzarcclefcrosqvakyoenughdadgmgdchgvjiinpleddvbfhzuloqtvvtabfihkpnfaxqqmburgrslathljxehvahwhsftjszkpradswxaqrlqlvewukdpmlouftnomoydfajzzgzpxnhkilhcykskxiecburpkrtsuctvktkhitsqhzuflopjwwnysgneaiwumqpwlbetwwldxfiiuatqwh...

output:

735652

result:

ok single line: '735652'

Test #41:

score: 0
Accepted
time: 779ms
memory: 566328kb

input:

4000
fcrfjdagkknhhvvklrmnnnqcrmjnifrphkwsnyaxiqfpnczytnngbejusuhabapjkodzmgwvydmlfomabzhedsywmhyohqzreeqqmpnkuawcoicrhlwndwjsehilzjfdnxwcmjmjjklzsptcbrpenaytjgfjpmmfjihyuvhfguhyjacktrrgrpadyhmptaueldcfzjkfdrfptizmbqvvixyiekxzmudxxgcwrpdxilmcvnqweltokrwqdtpsnvpndulujpttchxxvotzbppmilcmguewpvjupuoalku...

output:

555122

result:

ok single line: '555122'

Test #42:

score: 0
Accepted
time: 1001ms
memory: 777460kb

input:

4000
abbaaabaabbabbbbaaaaaabaaaaaaababbabbaaabbaaabbabaaaababaabaaaabbbbbbbbaabaaaaaaaaaababbaababababababaabbabaabaababbaaaabaaaababaabbabbabaaaaaababaaababbabbbbabbbbaaaabaabaaaaabaabbaaaabbbbbbaaaaaaaaaabbabbabbaababbaababababbabbbbbbbaaababbbaabbbabaabbbbaabbbabaaabaaaaabbabbbbbabbbaaaaaaababbab...

output:

777185

result:

ok single line: '777185'

Test #43:

score: 0
Accepted
time: 1113ms
memory: 802596kb

input:

2
baaaaaaabaaabaaaaabbaababbabbababbabbaabaabbbbbbbbabbbabaaabaabbbbbbabaabbaaabbbabaaaabbababbaabbbabaaaabaabbaaabaaabbbbabaabbbbababbabaabbabbabbababaabbabbbaaabababaabbbbbabaabbaabaaabbbaababababbaabaaaabaabbbbabbaababbbbabbaaabbbbbbbabababbaaabbbbaaabbaababababaabbbbaaabaaabbbababbbbbababbbabbba...

output:

54

result:

ok single line: '54'