QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#698265 | #3844. LCS Spanning Tree | yzj123 | AC ✓ | 1190ms | 804304kb | C++20 | 3.4kb | 2024-11-01 18:28:08 | 2024-11-01 18:28:08 |
Judging History
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 Suffix_Automaton{
int O,link[MAXN],maxlen[MAXN],trans[MAXN][26];
//link[i]: 后缀链接
//trans[i]: 状态转移数组
Suffix_Automaton(){O=1;}//根初始化为1
inline int insert(Re ch,Re last)
{
if(trans[last][ch]){
Re p=last,x=trans[p][ch];
if(maxlen[p]+1==maxlen[x])return x;//即最初的特判1
else{
Re y=++O;maxlen[y]=maxlen[p]+1;
for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
link[y]=link[x],link[x]=y;
return y;//即最初的特判2
}
}
Re z=++O,p=last;maxlen[z]=maxlen[last]+1;
while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
if(!p)link[z]=1;
else{
Re x=trans[p][ch];
if(maxlen[p]+1==maxlen[x])link[z]=x;
else{
Re y=++O;maxlen[y]=maxlen[p]+1;
for(Re i=0;i<26;++i)trans[y][i]=trans[x][i];
while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
link[y]=link[x],link[z]=link[x]=y;
}
}
return z;
}
}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.O; i++)
// {
// cout << "u:" << i << " ";
// cout << "col:";
// for (int x : col[i]) cout << x << " ";
// cout << "\n";
// }
for (int i = 1; i <= SAM.O; i++) g[SAM.link[i]].push_back(i);
// for (int i = 1; i <= SAM.O; i++)
// {
// cout << "u:" << i << " ";
// cout << "v:";
// for (int x : g[i]) cout << x << " ";
// cout << "\n";
// }
for (int i = 1; i <= SAM.O; i++) a[i] = make_pair(SAM.maxlen[i], i);
sort(a + 1, a + SAM.O + 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.O; i++)
{
vex.clear();
int u = a[i].second, val = a[i].first;
// cout << "u:" << u << " " << val << "\n";
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);
// cout << prtx << " " << prty << "\n";
if (prtx != prty)
{
prt[prtx] = prty;
ans += val;
k++;
// cout << "---------------val:" << val << "\n";
}
}
if (vex.size() > 0) cr[u] = get_prt(vex[0]);
}
// cout << "k:" << k << "\n";
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: 8ms
memory: 12200kb
input:
4 icpc macau regional contest
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 4ms
memory: 11856kb
input:
3 ababa babab aba
output:
7
result:
ok single line: '7'
Test #3:
score: 0
Accepted
time: 288ms
memory: 469928kb
input:
26 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 4ms
memory: 11848kb
input:
7 jia ran jin tian chi shen me
output:
9
result:
ok single line: '9'
Test #5:
score: 0
Accepted
time: 4ms
memory: 12016kb
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: 7ms
memory: 14240kb
input:
100 dblkekaekijliimalcaidjjfaghdmhifkiebieffbddjmflkhagajcfmkccjjadgiijdbdldgbbhgcfdcadbeiabkemiefdccmhdcfilhkfabmfdmigfgigdcibgaeicedfiidgecbhdamiaiefbmbgbjhklbhafmhckklbmmiemkcbfgjihmdjkai bciiecmbc cdjailkkbefkbmlekiefdhklcbdccfbgkagflfemjjmkjmcgiibldlmhbcldjajgafmakfbhecgcckkkglklljhmliehidbkicm...
output:
476
result:
ok single line: '476'
Test #7:
score: 0
Accepted
time: 870ms
memory: 578968kb
input:
2000 ecbhcebgbcjgjiihdefajfbbaajfjdedggciaegdiijhijgedbgejhgjjfhabdfhbihdeegcehbcjhgebcjachbdeiefejefhcjdihfcfgeegdahhjhjiiffjjadifiijjbhhjjeffabiaagcjhaachjbiecfeceefddecjchjfibgedfdghgdijdcdahfeddjihbhbbghjjffdcibaggiiadbaajhfcgdbaafbicahjhabfdbeacccfdehebciafaaffdfjdciafbhidbahdccjhjdadcciecfbhac...
output:
17765
result:
ok single line: '17765'
Test #8:
score: 0
Accepted
time: 894ms
memory: 553992kb
input:
1413 gjjmlceglbmbibjmmfcfmickcllfekgmicmifdbfgdgbeecgjgalbfkdfljjkclfgkaacdgigblaiaiehkeiccbjamikdgcjfemhhfebicddelklibjafmjhleebkimeblljfembgcgacdlkhjmbijjgacjaajebjfkcllffalheefeaedbmmkicaeecckdmedddbikeieimjmmcfdcgamicfbeimkjfamidjfhejdgiehkjkbdaaaeieldfibkkcgallieiamfehcdggiigkabblgigjgdlmflmafj...
output:
11429
result:
ok single line: '11429'
Test #9:
score: 0
Accepted
time: 69ms
memory: 28676kb
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: 735ms
memory: 534144kb
input:
2 adwkgmoosmodblpylbpymmnbzyjzddfegdqppefjstpueeurhjpuvdxudgtgmaksfdjwhogcivwmbqeiavcxybubknkwqwqxzaujoclyzhnaztibonzpotsaicwaznyapujfwugvdtxfmhgcuhrlcklnminnxnoojzvfwbczubgijnldwcqzocodmdqltgzcguicwmdsombxbmcxotyfvmijsaulhtnppxtnkygakhzltbjjwjqrwyaozwzgroxhmquyocazjzkecvqzfgqdhttgpuojilqwbmurruscvd...
output:
8
result:
ok single line: '8'
Test #11:
score: 0
Accepted
time: 1190ms
memory: 793248kb
input:
1413 ababaaaababbababbabbaababaabaaaabaabbabababbbabbaaababbbbabbababaaababbbaabbaaabaaabababbbbbbbabbaababbababaaabaabbaaaaabbbaaabbabaaabaabaababaaabbabbabaabaabbaabbbbbbabbabaaaabbababaabbababbbaaabababaabaababaaaabaaaaababbbbbbbbabbabaabbaabbbbabbbbbaaabbbbbaabbbaabababababaaabbaaaaabbaaaabaaaaa...
output:
42405
result:
ok single line: '42405'
Test #12:
score: 0
Accepted
time: 29ms
memory: 23300kb
input:
1413 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
1995156
result:
ok single line: '1995156'
Test #13:
score: 0
Accepted
time: 1032ms
memory: 803356kb
input:
1 baababbbbbaaabbaabbabaabbabaababaabaaabbbbbbbabbbababbbabaaababbbabbabaaabbbbbaabbaabbaabaaabaaaabbbabbbaaabbbbbabbbaaabaabbabbbbaabbbabbbababaaabaababaabbbababbabbbbaaabbaabbbbbbabbabaaaabaaaabbbaaabbbbbbaaabaaabbabbababbabaabbabababababbbbaaababaaaabaabaaababbbbbabbbaaaaaababbbbbababaabbbabaaaab...
output:
0
result:
ok single line: '0'
Test #14:
score: 0
Accepted
time: 753ms
memory: 589660kb
input:
1413 fnjfbnhskrerdxmxrlthhclkgcfrwukmccsfpbazsetxbfwvsseauqmcuutqofeshwxyxxasbtpfaocsgguayjcsdxitcnllliljglbjesqggubmbvozessjpcctrngdwsoedrpkjgsqatedrtfvlzhddjyvxfavxozcfooowhgzalctgjrriywmhvjeajzzxadepsslbbkdmpxsaoljmixvdgafpbgocjstdmegnrkbijvizjtnrqiwykdpmjfquxjympeziqdsbydahwpapyypkbfwmkohkxfwplv...
output:
464827
result:
ok single line: '464827'
Test #15:
score: 0
Accepted
time: 690ms
memory: 563956kb
input:
1413 vrotfwuoloxhchhuitgryunhjurviyookrumnoabeziigrdpmlglfvurrlmblapvtlkhbmkgmuosltjxerkkmfdfspgeqwbjhlslycrkwhehdohhhrtuwwbpmivegwppikaimtulbyugobnwvjsrhtivddzjcrbmbbupvoayoxefatdvexnmqxhwdjhfairbmlsjbvjrspwsibonydbrcinfrwkrfduropcrkljeahyijoxhryaujnzakmurpqkgfmxpxivzsuhbihkchnwsaxtmlpfbfphldgccrab...
output:
254582
result:
ok single line: '254582'
Test #16:
score: 0
Accepted
time: 615ms
memory: 741328kb
input:
1413 bbbbbabaabbabbbbbbaaabbaabaaabaabbabbaabaaabbbaaaaaabbaaabaaaabbabbbbbbbabbbbbabaaabaababbbaaabababbaaaaabbbbbabaaaabaaabbabbabbabaabaabaaabbbabbabaaababbbbbbaaaaababbabbbaabaaabaabbabbaaabaababaaabbbbabbabbabaaabbbabbbabbbbabaabbbabbbbabbbbaaabbbabaaabbaaaaabbababbababbbbbbaaaabaaaabaaaaabbabb...
output:
1498740
result:
ok single line: '1498740'
Test #17:
score: 0
Accepted
time: 483ms
memory: 509084kb
input:
1413 lcoqmejczgztniltuwtqgzmgyjdvkiqvlgozlzdmhchwksqerjuxkigjslgetycefqfqriezkmvwgndxyzvjiducocihbkogctyuecvqqqnxgsuerrpbwldkooupyixbdvxjzsaskppqhlvafmcbyfmmtgduqaxvxwfwohoawftfrofwahxyplmktpglrfjobolpxbsvhlaabhydrxeijqueibqzgzoipbzmctjlelnfsllllptufqaptqpzrdjgeluigdwlolsjzdwkusgcigrbzgcqlozpbvahzys...
output:
1285703
result:
ok single line: '1285703'
Test #18:
score: 0
Accepted
time: 686ms
memory: 552180kb
input:
500 eqrouzrzqavpwipjhbpbbsypakjkmpithzhdazdqzyivgzhpawsdorsrdcdstllansenrjgsjqqspxhrvaumtnfwrioktzmiusynbegluwdlvmcsoyghlleetuopwdzqxxdzdlmzjrkgdozunhbythfoetdaydswcxxgllfucsbhgcbtjduemztquysvdkrikqovbvpdnsmuwopitjmhkhyfiqaldtvnjjikhzpwubsqriymtnueuulcmnqrglepxobgqqcktvaldbzwovcirnneafvisczpsavisauo...
output:
93437
result:
ok single line: '93437'
Test #19:
score: 0
Accepted
time: 1006ms
memory: 798604kb
input:
500 aababbabbbabbbaabbaaababaabbabbaaaabbaaababababbbbbbbaabaaaabaabaabaababaabbaaabaaabaaaaabaababbaabaaabaaabababbabaabaaabaaaabaaabaabbabbbbababbbbbbabbbbbabaababbabaaaaaaabaabababbaabbbbbbbaaaaababaababaabbaaabaabbbaaaabbabbabbbbaabbbbaaaaabaabbabbababbaaababaaabbbabbabaaaabbaabbababbbbabbabbbaa...
output:
621482
result:
ok single line: '621482'
Test #20:
score: 0
Accepted
time: 547ms
memory: 530024kb
input:
500 xkhhkzemvoilwwysloxrngtnalowphqotywezcsuqahpwhjjwjalpvysipqxyhoshkyioqchqlyothxrqacivacersdqbrkkdisuywdqibgdidwbfylbanhsfmkjgutlemfeiiusjaxuftvltgoutxoajajpwfbatiedtawcavwhptsizieufsxpuigqnjqguwknwirydqgujadlljfqeehynopazfhtetgabazgqhbzjgkupsltwusjijmkqtduomvpmwvcfydoeoluiypesjqbscnjxqdleacsyzwd...
output:
1305055
result:
ok single line: '1305055'
Test #21:
score: 0
Accepted
time: 472ms
memory: 526716kb
input:
500 afdppltdvwipholvfwehnlbcmcxujuxlbabqnwtiudzbunzzjfiwqjzclyzwswiuylmmjiwdlygflfhumrtcbuhosgnmexieivsrdpuopcwckdywwrzxliofqdswacaixtbckxtzzpbjubgqthqgrgmhjgdjidtiyukitdhuukeqmmhhvzpmfbvqjazsfuceqomjuwdoijhwvodqptewwzmgznafhejxsvimtldcvkasagjpbnnzpbhoohtxnewgceuvrxzojahjgsajhniwoqlezgbnlzvndpixpkly...
output:
1248710
result:
ok single line: '1248710'
Test #22:
score: 0
Accepted
time: 716ms
memory: 589340kb
input:
4000 gdlglqbydbkucqucvkhjoicbrutfyulgywmlpqlurxpvqhkywpnnwerqgjnnxyheruhcotfjpohhyrfwiulgbcyjnnwlofrfcykqspchfjqfcyemupuvutghifuykmeokohcfjlmueuycykwpeujzctkhpibmfvorjdmqztnqyqzjgzcsekanoxzescqxxeojjczivoywhzhpzjhftkvjhunzwfzwlphvsifpweldfstgdcoymjktfzvdfubqlilfqrvpxiuednlgqzhekrypstuxpwqagbgzubotli...
output:
587656
result:
ok single line: '587656'
Test #23:
score: 0
Accepted
time: 687ms
memory: 702380kb
input:
4000 baabaabbababbbbbabaabaabababaabaabbbabbaaaabbbabbaaababbbaaaabaababbbbbbbbaaaaabbabaabbabbabaabbaaabbbaaaabbbbaabaabbbbaabbaaaaaaaaaaaaabbbaaaabaabbbabbaabaabaaaaaabbaaaaabaaaaabbbaaaaabaabaaaaaaabbaabbaaabbaabaabbabbbaaaaaaabbbabbbabbaaabaababbaaabbaabbababaabbbbaaaaabbaabbbaaabbabababbbbbaaaa...
output:
867646
result:
ok single line: '867646'
Test #24:
score: 0
Accepted
time: 734ms
memory: 704640kb
input:
4000 baaaabbabbaaaabbbaaabbababaaaababbbaaabbbbbbbaabaabbbbbbbbbbbabbaabaabbbaabaabbaaaababbbaaabbbabaababaababbaaaaabaabbbabbababbbbbaaaaaaabbabababbaabbaaaabbbbababbbbbbaaaababbbbbbaababbaabbaabbbababbaabbabbaaababababaaababbbaaabbaababbbbbaaaabababaabbabaabaaaaabbaaaabbababaaaaaaababaabbbbabbbabb...
output:
870160
result:
ok single line: '870160'
Test #25:
score: 0
Accepted
time: 469ms
memory: 511236kb
input:
4000 jnbnjwgrxbxyqkbxyktdciatkisupcgkaanotwsywpwnczkakgfmohiypavecbrddgrwemuadsphrchdioswvaxnastcvmhasbwynsbsmqafsjjcybzvbwidqchnqpnjqjjfdkzpbzuvldyjgzejxpmntuajlpufrlzkaisoonwikhonlrvvrqszrenfgtmyeokhwcxkrwtbdjqqalltddvvhicqbroifyrbcootmjwrsmhuxspdykahscxwtnganxepnskabgrvuzrutgxttxdlbajvqpvdmbtatfc...
output:
913862
result:
ok single line: '913862'
Test #26:
score: 0
Accepted
time: 38ms
memory: 25268kb
input:
4000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
1979531
result:
ok single line: '1979531'
Test #27:
score: 0
Accepted
time: 551ms
memory: 547256kb
input:
4000 fdhdijdfcdeedcbjgafdgcdegdbibaahdhaeifbdafhfhaefacigedcdhfbifdhbcjhaeidhdccdchicbjafceabjdchgjaabhbffgcajhdbecghdiehffjgiddhcfhdcabhhfigcdjihffagaibhjhhcdegiecbedabaajdgjbefbdbadcdeefgbibbhgaedhbhjgejchfjiididfcibjefhfgebiagfdfejjgbhdcfefghdafgjbbijaeciebghgcgiijhedeijahecfabgcbhefacbbaijdghdhe...
output:
1228665
result:
ok single line: '1228665'
Test #28:
score: 0
Accepted
time: 514ms
memory: 518580kb
input:
4000 rjdknocpagvrnghrpyukwifkkddprokianvndxdwgczcauhwrkpqmhqsmxqpmoxhazmujpspurtwndsfphxcrnwfnmuzauictvwfmowghscvvwckgzoxnkcawybzukbohyvtmrcwjgrgdvzovoosphzmirifzwmbfzuauwkmgoaodbfasvtjcuxmnftmcfohhkhdgtppkrfnvmpnhiwletasztebbskidtnjocaywgnrsdecnapsvpkuloxojjymelxtpyrlgfcakiexkurglbcwscmblkpqvmjlmcw...
output:
911422
result:
ok single line: '911422'
Test #29:
score: 0
Accepted
time: 401ms
memory: 330648kb
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: 381ms
memory: 319512kb
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: 336ms
memory: 278724kb
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: 32ms
memory: 31200kb
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: 575ms
memory: 566252kb
input:
20 cqhcbnnuobmgcqfdzbuvyajaidogyrtcjbemouifxulzlqcmtwiryttiwhpuykxjldvaxefuastnkvaeukxsdtdcauwbevkqziswmzrmrmabkchemhyrabtavqdajwzphqhuggbrujigzfhqxcrtcifvvvfgrevavfwdlauhjenkjudgyubcfhxcccivjfyemujywfhfjxsutvcsreuwnuypwimfqmlcjucfzklkhdeaahurnrqalqrjzfrrsctbzygaktltyrvyyqsnjinwyghzmyqgdmhekpeulrnjj...
output:
201946
result:
ok single line: '201946'
Test #34:
score: 0
Accepted
time: 765ms
memory: 801792kb
input:
20 baaababababababbaaaabababaaaabbabbaaabbbaabbaabaabbbabaabbbabbaabbbbabaaaabaabaabbbbaaaabbaaaaabaaaabaabbbbbbaaabbbabbaaaababbbbbbbaabbbababbabaababaaabbbbaabbaaaaababbbabaaaaabbaabababaabbbbabaaaaaababbabbbbabbabaaaabbaabaabaabaaaabbbbaaabbbbabbababbbabbbabaaaabbbaaaaabbbababbaaabbbbaabbbbbbabba...
output:
187803
result:
ok single line: '187803'
Test #35:
score: 0
Accepted
time: 492ms
memory: 532228kb
input:
20 wighspqotssudabkedkygymrryunfudbdlkxbdnwxfqbitnmwxmeyyypysfgoihtuuqxxgtullvvgjhcivigwiyucdatnkmhefgblbxymtusedwozhxxrvruaunngbxkifnvhkwvfqolvmawvxtnunjuhwjnzizioofvabqgtgtpvtnqshfmwoidmssmatwohblhdepwmjnhcbavkfjgwslikfumysdfwombscxfnnopqomcwyksqvaaaxoaprflgtmaxmfkbwcrkqtgodaeabgcyvepmjduervefcqgy...
output:
265680
result:
ok single line: '265680'
Test #36:
score: 0
Accepted
time: 58ms
memory: 65916kb
input:
20 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
1799368
result:
ok single line: '1799368'
Test #37:
score: 0
Accepted
time: 1044ms
memory: 804304kb
input:
2 aabaaabababbaababaaabaaaaababaabaabaabaabbbbbbaabaaabaabaabaabbbbbbaaaabbbabaabbbabaaabbaabababbbbbbbbaaabbbbbaabaababaabbabaaabbbbaabaaaababaaaabbaaaaababbabbbaababaaaaaabaababaaaaaaaabbbaaaaaaaaaaaaaabaaaaaaaabaabbbaabbabbabbabbaabbaabbaababaaabbababbbbaaaababbbaababbaabbabbbabaababaabaababaaaab...
output:
92934
result:
ok single line: '92934'
Test #38:
score: 0
Accepted
time: 712ms
memory: 557212kb
input:
2 jcmgevxqwiaflstvldrnmkeoeczrruqbxfjdagtyptfcoyybepqqzvggxgxpcpsbubfxhyvyubbkbznfqdysyeywmxlrodslgxipyfougrgkstriwpavwatkzgbolwbrtjgtownxnthfoyqlqsimvbwuhakuwllrurllqakdwtlkrdvjvfvqiunruxlslwjhqwsgzcjvvwfpzdyxkwntqakmawglurskonqnpcknarecwezhaoasrmgrkmefgwpujijbmvqomwqjarsbguvxgcqrqwwwsnsexdhjazanvq...
output:
91737
result:
ok single line: '91737'
Test #39:
score: 0
Accepted
time: 138ms
memory: 454376kb
input:
2 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
93662
result:
ok single line: '93662'
Test #40:
score: 0
Accepted
time: 685ms
memory: 590568kb
input:
10 cdvthwmepkhrkkvpucesqgrdwtzdvicynxrutfykridcsbrpfvhwdabzucdpkhpxhgtcospfashuvajdxqzarcclefcrosqvakyoenughdadgmgdchgvjiinpleddvbfhzuloqtvvtabfihkpnfaxqqmburgrslathljxehvahwhsftjszkpradswxaqrlqlvewukdpmlouftnomoydfajzzgzpxnhkilhcykskxiecburpkrtsuctvktkhitsqhzuflopjwwnysgneaiwumqpwlbetwwldxfiiuatqwh...
output:
735652
result:
ok single line: '735652'
Test #41:
score: 0
Accepted
time: 663ms
memory: 561608kb
input:
4000 fcrfjdagkknhhvvklrmnnnqcrmjnifrphkwsnyaxiqfpnczytnngbejusuhabapjkodzmgwvydmlfomabzhedsywmhyohqzreeqqmpnkuawcoicrhlwndwjsehilzjfdnxwcmjmjjklzsptcbrpenaytjgfjpmmfjihyuvhfguhyjacktrrgrpadyhmptaueldcfzjkfdrfptizmbqvvixyiekxzmudxxgcwrpdxilmcvnqweltokrwqdtpsnvpndulujpttchxxvotzbppmilcmguewpvjupuoalku...
output:
555122
result:
ok single line: '555122'
Test #42:
score: 0
Accepted
time: 876ms
memory: 776684kb
input:
4000 abbaaabaabbabbbbaaaaaabaaaaaaababbabbaaabbaaabbabaaaababaabaaaabbbbbbbbaabaaaaaaaaaababbaababababababaabbabaabaababbaaaabaaaababaabbabbabaaaaaababaaababbabbbbabbbbaaaabaabaaaaabaabbaaaabbbbbbaaaaaaaaaabbabbabbaababbaababababbabbbbbbbaaababbbaabbbabaabbbbaabbbabaaabaaaaabbabbbbbabbbaaaaaaababbab...
output:
777185
result:
ok single line: '777185'
Test #43:
score: 0
Accepted
time: 1040ms
memory: 803804kb
input:
2 baaaaaaabaaabaaaaabbaababbabbababbabbaabaabbbbbbbbabbbabaaabaabbbbbbabaabbaaabbbabaaaabbababbaabbbabaaaabaabbaaabaaabbbbabaabbbbababbabaabbabbabbababaabbabbbaaabababaabbbbbabaabbaabaaabbbaababababbaabaaaabaabbbbabbaababbbbabbaaabbbbbbbabababbaaabbbbaaabbaababababaabbbbaaabaaabbbababbbbbababbbabbba...
output:
54
result:
ok single line: '54'