QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #141242 | #6516. New but Nostalgic Problem | cy1999 | AC ✓ | 136ms | 157504kb | C++20 | 1.2kb | 2023-08-17 09:57:11 | 2023-08-17 09:58:02 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int son[2000005][26],n,k,t,sl[2000005],res,siz[2000005],idx,sks[2000005],fa[2000005],fc[2000005];
char lx[2000005];
string s;
stack<char>q;
void ist(){
int nw=0;
for(int i=0;i<s.size();i++){
int c=s[i]-'a';
if(!son[nw][c])son[nw][c]=++idx,fa[idx]=nw,lx[idx]=c+'a';
nw=son[nw][c];
}
sl[nw]++;
}
void dfs(int x){
int nw=sks[x];
for(int i=0;i<26;i++){
if(son[x][i]){
sks[son[x][i]]=nw;
dfs(son[x][i]);
nw+=siz[son[x][i]];
siz[x]+=siz[son[x][i]];
fc[x]++;
}
}
if(sl[x])fc[x]+=sl[x];
siz[x]+=sl[x];
}
void solve(int x,int nw){
int rt=nw;
for(int i=25;i>=0;i--){
if(son[x][i]){
solve(son[x][i],nw+sl[x]);
nw++;
}
}
if(fc[x]+rt+sks[x]>=k)res=x;
}
int main(){
cin>>t;
while(t--){
for(int i=0;i<=idx;i++){
fc[i]=sks[i]=sl[i]=siz[i]=fa[i]=fc[i]=0;
for(int j=0;j<26;j++)son[i][j]=0;
}
idx=0;
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>s;
ist();
}
dfs(0);
solve(0,0);
while(res)q.push(lx[res]),res=fa[res];
if(!q.size())printf("EMPTY");
while(q.size())printf("%c",q.top()),q.pop();
printf("\n");
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 13832kb
input:
2 5 3 gdcpc gdcpcpcp suasua suas sususua 3 3 a b c
output:
gdcpc EMPTY
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 102ms
memory: 13860kb
input:
20000 5 3 apveofpr irdbqk rnionnjjrk wrpihlsw ofylfsriof 5 4 iiltghqg kybhogptqf jfnmqxzrdq rpztcluq tzmnrcjae 5 5 ysp vujmkkcutl ksawqeiiaf waukilaq wmlsutlued 5 3 pikybt yiqmqvtjeq tyrsoihf vnvjrxpus cuubpacubb 5 2 rihuvikhg twrsuoervz ukiekoohw eysqgndpf sxswpeqtaf 5 5 vxzhicbp nvtdbgqal jilppvpt...
output:
EMPTY EMPTY w EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY o EMPTY EMPTY EMPTY EMPTY EMPTY t EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY w EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPT...
result:
ok 20000 lines
Test #3:
score: 0
Accepted
time: 93ms
memory: 13828kb
input:
1000 10 9 wkpbdhbivgksnwvnqnynzrmhowmpbbtswjydwidifwuquenplmozlqnkxqefckyzcughrdbturdzsxrcggpzrtrvlewigox qbxgxomnfarjtvfbxbabtpmhnuwvbxfpwpkjuzjsehofemfzxglvvthzgkzukwmlyfhajchvphdjfqmfubwwpdtdbjpfvk qrsovcdbphsndcmjwxjhmktwvgakzqewnoymumlawlmmgjmbpivccldrrfgspjypwosdqgpyqnxhaukwycqntuxglbdwf fbdtn...
output:
q EMPTY EMPTY EMPTY h EMPTY EMPTY EMPTY h EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY v b EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY t EMPTY EMPTY e EMPTY b EMPTY EMPTY EMPTY EMPTY EMPTY b EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY v EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPT...
result:
ok 1000 lines
Test #4:
score: 0
Accepted
time: 132ms
memory: 13828kb
input:
25000 10 8 phl vwel ufme dtsf con giby xlma dhke zjir itws 9 5 qtgd wcqj ixmz swv myxo eqq yxiq uvb spbw 10 7 xrkp ze smt nq ijhw lmxf kcgs hi qwmq hilw 8 7 rlf taaq hmdu thex dbb spcp awyn khdu 10 10 voxx tqv ehtx xctk zamh zua rbyg bmeh wmiv cmw 9 6 bzq ayz cdna myi rdeu gtdo ycy sjec ystp 9 4 tix...
output:
EMPTY EMPTY EMPTY EMPTY z EMPTY EMPTY s EMPTY EMPTY EMPTY EMPTY EMPTY y EMPTY EMPTY a EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY m EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY g EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY j EMPTY EMPTY EMPTY EMPTY EMPTY j EMPTY t EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY ...
result:
ok 25000 lines
Test #5:
score: 0
Accepted
time: 100ms
memory: 101712kb
input:
1 898 840 fdefauodwerznqpzszernrspbndmdfkjrbazmworfvlfbxwcprhxenouzxirrhqtwgiwdcejexotjetwgzqlqtndynfzwmfakfeojtxwrvekebmudrouskcgpzncnsxwajwaoclvqnaycgaaktqctsmbnosbajzryxpxzxuwnzpvmyfobgogbllqyxplageeufjjnrlhairtetyridmhthpplivokbinfmblugrzkcyxuhewtyoxkfzmyhgsbafmgqazoqollibsxlprjneeqursjuomypstme...
output:
y
result:
ok single line: 'y'
Test #6:
score: 0
Accepted
time: 47ms
memory: 13856kb
input:
1 666416 645656 d j s g s b w x b z v m c o h a j v v l y i l n g x u q d m z q k n l c v n q b y g t c q i k b z i h e c b h e v a n c n z b g c n m f x q y b l h r a i g v e q k u e z q a a a c g d c d f n i d l d w i h p b a u n i e z l v l a y t k j y z r f c o f x w p y q a j v j n t f m j j z ...
output:
z
result:
ok single line: 'z'
Test #7:
score: 0
Accepted
time: 129ms
memory: 157504kb
input:
1 10 8 tahlarajyplchghlbufhsanuvbmsafotmdanvtsltpignbmcydrndrjteyjjphxzxjcsqnszqxhmcyvujrfdispekvglqxyeflsvdssvmrkfjvyydknxjcyekcstfzgpnznkupdsaesmhakazgshvycwwctjnwxhhdokcujhwnqrqyqnvfikaofgwyxfcphgpkayzzwgcmceycippdyvibeqqibhemzeucugdtwlljqejewmapdajieanbukrpeqfzlcqblbkbemvcvkdnwshnbhymextgudifvju...
output:
tahlarajyplchghlbufhsanuvbmsafotmdanvtsltpignbmcydrndrjteyjjphxzxjcsqnszqxhmcyvujrfdispekvglqxyeflsvdssvmrkfjvyydknxjcyekcstfzgpnznkupdsaesmhakazgshvycwwctjnwxhhdokcujhwnqrqyqnvfikaofgwyxfcphgpkayzzwgcmceycippdyvibeqqibhemzeucugdtwlljqejewmapdajieanbukrpeqfzlcqblbkbemvcvkdnwshnbhymextgudifvjupdzdlne...
result:
ok single line: 'tahlarajyplchghlbufhsanuvbmsaf...zlcmnrtuhonflpulivygwfecgknnhvx'
Test #8:
score: 0
Accepted
time: 109ms
memory: 116056kb
input:
1 10 3 fbggdpqikbolemnowgfpwwouvbmhhxhecicbinhjesduugcuztgbjleluktdtbpcjfrwowpjfnkutjiffhdgygavviinleqwungdnykbnhrnccqnzbtaaouommlictujvlytueosbalqanancqjojunivkmzbhnggvraxlyowgdovaogsqdzxutwmcqwqrawlnxagzztmsxvrmhsrybddgtpboflhbbojoiolrhmhrvgyxuputssivbrlsdxvwbraxxtgugamtcorgeiazpvomjlkefldsvntaxpf...
output:
fbggdpqikbolemnowgfpwwouvbmhhxhecicbinhjesduugcuztgbjleluktdtbpcjfrwowpjfnkutjiffhdgygavviinleqwungdnykbnhrnccqnzbtaaouommlictujvlytueosbalqanancqjojunivkmzbhnggvraxlyowgdovaogsqdzxutwmcqwqrawlnxagzztmsxvrmhsrybddgtpboflhbbojoiolrhmhrvgyxuputssivbrlsdxvwbraxxtgugamtcorgeiazpvomjlkefldsvntaxpfaxlmbsj...
result:
ok single line: 'fbggdpqikbolemnowgfpwwouvbmhhx...wwjgvkuxmlyqdleytyumnytyslycfmz'
Test #9:
score: 0
Accepted
time: 67ms
memory: 83324kb
input:
1 100 64 bqrjaovelwrainyujustjcnoyqpyeuqtpwbgafxsdcmjqbgbrqkzbwejfhxswzqjjibagmdkasztqqhxsubyliuwzetglnccigmzrhxrmrrptvywyavwpkqqsyhyuhdtstkqzlqbzvpacuevwrpinfzubzjgj bqrjaovelwrainyujustjcnoyqpyeuqfwuhsdtwgclvkdqobrrofezdyylsoddrsaxewflgjfmzreabpqstcfdmlkcfkhriuwkqfcodelppbuxxqxpanwsewtrnccauewokmq...
output:
bqrjaovelwrainyujustjcnoyqpyeuqfwuhsdtwgclvkdqobrrofezdyylsoddrsaxewflgjfmzreabpqstcfdmlkcfkhriuwkqfcodelppbuxxqxpanwsewtrnccauewokmqqahhykfsawtiatqczizqtmabdxqotpzhufebenhmnmbkavtbaqkpjloblntpbjhazyjtkakpeydymjnhgfsojzzucjvehkuvnefhkytpaasskzteisyylpukgkerhneqjqjkkqkigljadrneojmeyebyissomxlopckhtqz...
result:
ok single line: 'bqrjaovelwrainyujustjcnoyqpyeu...ulctwnloovccolzzlgjbonxkmtsflyq'
Test #10:
score: 0
Accepted
time: 73ms
memory: 82276kb
input:
1 1000 655 xrivmcvikmllrgissoqginwxkoqyxywrvspoagwvuycscxxldlmrszeuiiqzbcvkyvcogtqagprfubjza xrivmcvikmllrgissoqginwxkoqyxwsgqbhhyygxeboxmuseokzosgqwekpchzsatkqlfiffshydwxtetdvwksuotvzaeosixlrlnoqdidbtocqkfwinselyycwpyxwywucccqorepmqsrncceebgbtygqrtviddhsqzpxauobucvondytzflgphhqgxkyaoihvvrqrvkbbleyn...
output:
xrivmcvikmllrgissoqginwxkoqyxwsgqbhhyygxeboxmuseokzosgqwekpchzsatkqlfiffshydwxtetdvwksuotvzaeosixlrlnoqdidbtocqkfwinselyycwpyxwywucccqorepmqsrncceebgbtwiulbxpgqmqazceacggpluxdaxnjcrvcfxzthnkvjegomnbsmbfksetqxuxukwooizgrmgupxlnspeovfiuqyndkkgrzjwxxvpjopmjhknuavonvknpcxwlcjnvrdrvvqxinzktygkkjdhdoewkwx...
result:
ok single line: 'xrivmcvikmllrgissoqginwxkoqyxw...vsirnpcffpggcsscctonqrzhktybdfd'
Test #11:
score: 0
Accepted
time: 84ms
memory: 85936kb
input:
1 100000 60101 wbpwp wbtpv y wbmwmw wk wbi wpr wbmxw wms ttch x z wld wbmyu e wbmy ywa ws yw wv wbq ya x wx zp yl wt x wbddy wbwu y j x wbsvn x y y fwf wc yf z wcz ys wt z y xke zy wbt wbmwmvnoku wbu wbpikxn wbmx z x wbr zqt wbf wbq wr y z ye x y wtt ys wam z z yd wbmwzjdzk y z z wbpb wbtua z z x z ...
output:
x
result:
ok single line: 'x'
Test #12:
score: 0
Accepted
time: 136ms
memory: 149576kb
input:
1 15 3 accbbabccbbbaacaaabaacbacccbabaacbcbbaacbcabcbcabbbaabbbacaccbcacacbacbbbccbacaaabbaacbacbaacbcbbaaccbcbccbaabcbaacaccbbbccbbbccccbbcacacabaabccacccbcabacbbbbacbcaaababbbaacaababccbcacabcbaacccaaabbbcbcbcaaacabaacaabacbcbbccaabaccbbcbabcbcbabaabbbbabbcaacacbbcbabbabccabcbbbcbbbbcbaabcbcbacaba...
output:
EMPTY
result:
ok single line: 'EMPTY'
Test #13:
score: 0
Accepted
time: 43ms
memory: 22480kb
input:
1 300005 2 dei ytd scz rkd csj vhk spe vmf dep dhi afl vmyl xfg nno lgg gexx myx dhl ytk bdo sna znd xkm opt lwm ewr nsdtw pbx rqy dplgd znt sbw lga kvm xfe ewb dpz lyk spo ese dhb lcw jcb dhu poh lzw kybca ytw sbez eyx pfv sblv gew hcq yvi spy ewn spb znx xzn klj mna klp deuw ugv igu sbna yjli lwv ...
output:
EMPTY
result:
ok single line: 'EMPTY'
Test #14:
score: 0
Accepted
time: 116ms
memory: 142148kb
input:
1 8 2 aljyvnpjccrahfrixfoayvhxhwovfhsrjubibgwlxyhoryqxqlqbbpmszyogtslzmddmwkzwhjvnazabmzqeridgsukgosptmmbemzdfaezqiqedslcjkrlhjikiyzymeulnzxpnhhpbqnbdoqybnsbhesbgqbwfwyuggfnmeiceupezyjtzxhfspwrxnynxbeizewzejejkdfenecqhymgrvdgehzvahevwasmuboqwvblgbahyykskhiqtegqqylhknpbxxspyupyjufonsatqroxunkzenqoagq...
output:
EMPTY
result:
ok single line: 'EMPTY'
Test #15:
score: 0
Accepted
time: 124ms
memory: 144160kb
input:
1 10 5 badcbbacebabaaaaedeebfddecfcdfaccdeccdaffeaddafebdbedacabebbdacffdfeefebaabcbcafafbedacfbcadacfbeabafbeafdeacbdcfafcdfbbacbcbcbedecaedffceeccdfccdebaeeabfccbfdbebacfcebcebfafcfefaddfcacadccdfcfcefebbecdebadabffffecfcdababaddeeddfeccbbffdfabddaedeebcacbadbaadfaebaaaeecadfadbdadcdbdbbcbbfdeacdf...
output:
EMPTY
result:
ok single line: 'EMPTY'
Test #16:
score: 0
Accepted
time: 106ms
memory: 99916kb
input:
1 1005 796 fcfacbaaedfebebafefcaddfcbdeaeadcefdcebaabefbcfcaeddeebabaacbabdadaacfdaafdeebccfcbbffbecebfaaebdbbbbfcdadacfdababacaaacfdfcbdfeefeffbffadffcbbedfebdeefdeeeedcebeaecdbccdecdaefcfaccbabcaebdddffefeedeeafebaceafcdbadeaddcdfeaddafaaeccddbadefadafeebeccbfbceffaaddfbbbacfdacbeadcbeedcdfbecdfab...
output:
fbdfcffefdfefdabbbaaabbbdadbaecbbbfdaeaaefadaaeaacdaeecacfeccccddbedfdacaacdbdcdcaacecbbaabdccadfafdbdbdadbebfaafaeaaaacdecefdecefccacedeabcceabcfbcdeefbcabeddaeedbdaedacbeebaccbefddcdfcbaeaddfdfadadfadcbebccfbbbdbadcecfaceeefcfaebdedebdefdfaeefcedcffaeebcecbffacdcfcefefadaafbfdbadecefbfbfdceebbfcaff
result:
ok single line: 'fbdfcffefdfefdabbbaaabbbdadbae...fadaafbfdbadecefbfbfdceebbfcaff'
Test #17:
score: 0
Accepted
time: 81ms
memory: 100032kb
input:
1 1005 23 ecdafdebadceaebcadfaddbadfcbffbfaafdefecbfbceefaeeccabdaefefddfdccbcbeaeeefdedbadfcacedfabefeabcfdfcfadddadfeeeefcfeedcdcffeaedaffcdabecaecacaebddeaabcaabcebffeecafccdadacbbecbefedeefbebddcbadfdffdfabacddcdefeebddaddfdebafeffdeecaaedafebaceedfacadcdfcbdeafaaeeefcedcfdebfcbaddbdaefceaeafdca...
output:
adbcdacebaebdabbecbfdaebffefcfeaeafdaefefcffcbeeafaeebcfeddfaaaeecbabdbebeeaffebaebbfeeeafbfbfcacbdabbcafcecadbdcdccdddabaeeaacbcdfcbddbccdcaeaeeedcfefacddcbffcefbedabddddfaaffabffcbdbeafaceaaaadabeebbdedcbcbaceffcfdcfafbaeedaabcfabecfecacecdffccbaefabebceedcaadabcfbdbaeabfdccbbbeacefedbbcfbedfddbefae
result:
ok single line: 'adbcdacebaebdabbecbfdaebffefcf...abfdccbbbeacefedbbcfbedfddbefae'
Test #18:
score: 0
Accepted
time: 94ms
memory: 108588kb
input:
1 7 2 bebadebdcebccacabcabeebeebddebcaeceeebeeeadcaccecbccbeecbacbabbedcebdecebaacbedecdbdadcdbeacbabacbdaccbeacaaedeecbadecdabcaaeeecceebeaddbedeeeedbabbdebeddaabcaeeeaeeaeedcbbbbbdabbbdebaaaedaedcbabdceadcdbaaabdecdeabcbbdcbdaceacaddabbedbcadaeaeeedaaedcbeeebebcbceabecdbbcebadadcecddbbdeecbcdbedbb...
output:
EMPTY
result:
ok single line: 'EMPTY'