QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#482982 | #4224. 串 | zyxawa | 60 | 203ms | 152552kb | C++14 | 1.1kb | 2024-07-18 08:29:42 | 2024-07-18 08:29:42 |
Judging History
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