QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #141247 | #6516. New but Nostalgic Problem | cy1999 | AC ✓ | 178ms | 156192kb | C++20 | 1.2kb | 2023-08-17 09:58:48 | 2023-08-17 09:58:57 |
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");
}
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 13808kb
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: 133ms
memory: 13836kb
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: 100ms
memory: 13760kb
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: 178ms
memory: 13812kb
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: 109ms
memory: 101600kb
input:
1 898 840 fdefauodwerznqpzszernrspbndmdfkjrbazmworfvlfbxwcprhxenouzxirrhqtwgiwdcejexotjetwgzqlqtndynfzwmfakfeojtxwrvekebmudrouskcgpzncnsxwajwaoclvqnaycgaaktqctsmbnosbajzryxpxzxuwnzpvmyfobgogbllqyxplageeufjjnrlhairtetyridmhthpplivokbinfmblugrzkcyxuhewtyoxkfzmyhgsbafmgqazoqollibsxlprjneeqursjuomypstme...
output:
y
result:
ok single line: 'y'
Test #6:
score: 0
Accepted
time: 45ms
memory: 13812kb
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: 157ms
memory: 156192kb
input:
1 10 8 tahlarajyplchghlbufhsanuvbmsafotmdanvtsltpignbmcydrndrjteyjjphxzxjcsqnszqxhmcyvujrfdispekvglqxyeflsvdssvmrkfjvyydknxjcyekcstfzgpnznkupdsaesmhakazgshvycwwctjnwxhhdokcujhwnqrqyqnvfikaofgwyxfcphgpkayzzwgcmceycippdyvibeqqibhemzeucugdtwlljqejewmapdajieanbukrpeqfzlcqblbkbemvcvkdnwshnbhymextgudifvju...
output:
tahlarajyplchghlbufhsanuvbmsafotmdanvtsltpignbmcydrndrjteyjjphxzxjcsqnszqxhmcyvujrfdispekvglqxyeflsvdssvmrkfjvyydknxjcyekcstfzgpnznkupdsaesmhakazgshvycwwctjnwxhhdokcujhwnqrqyqnvfikaofgwyxfcphgpkayzzwgcmceycippdyvibeqqibhemzeucugdtwlljqejewmapdajieanbukrpeqfzlcqblbkbemvcvkdnwshnbhymextgudifvjupdzdlne...
result:
ok single line: 'tahlarajyplchghlbufhsanuvbmsaf...zlcmnrtuhonflpulivygwfecgknnhvx'
Test #8:
score: 0
Accepted
time: 95ms
memory: 115940kb
input:
1 10 3 fbggdpqikbolemnowgfpwwouvbmhhxhecicbinhjesduugcuztgbjleluktdtbpcjfrwowpjfnkutjiffhdgygavviinleqwungdnykbnhrnccqnzbtaaouommlictujvlytueosbalqanancqjojunivkmzbhnggvraxlyowgdovaogsqdzxutwmcqwqrawlnxagzztmsxvrmhsrybddgtpboflhbbojoiolrhmhrvgyxuputssivbrlsdxvwbraxxtgugamtcorgeiazpvomjlkefldsvntaxpf...
output:
fbggdpqikbolemnowgfpwwouvbmhhxhecicbinhjesduugcuztgbjleluktdtbpcjfrwowpjfnkutjiffhdgygavviinleqwungdnykbnhrnccqnzbtaaouommlictujvlytueosbalqanancqjojunivkmzbhnggvraxlyowgdovaogsqdzxutwmcqwqrawlnxagzztmsxvrmhsrybddgtpboflhbbojoiolrhmhrvgyxuputssivbrlsdxvwbraxxtgugamtcorgeiazpvomjlkefldsvntaxpfaxlmbsj...
result:
ok single line: 'fbggdpqikbolemnowgfpwwouvbmhhx...wwjgvkuxmlyqdleytyumnytyslycfmz'
Test #9:
score: 0
Accepted
time: 88ms
memory: 81448kb
input:
1 100 64 bqrjaovelwrainyujustjcnoyqpyeuqtpwbgafxsdcmjqbgbrqkzbwejfhxswzqjjibagmdkasztqqhxsubyliuwzetglnccigmzrhxrmrrptvywyavwpkqqsyhyuhdtstkqzlqbzvpacuevwrpinfzubzjgj bqrjaovelwrainyujustjcnoyqpyeuqfwuhsdtwgclvkdqobrrofezdyylsoddrsaxewflgjfmzreabpqstcfdmlkcfkhriuwkqfcodelppbuxxqxpanwsewtrnccauewokmq...
output:
bqrjaovelwrainyujustjcnoyqpyeuqfwuhsdtwgclvkdqobrrofezdyylsoddrsaxewflgjfmzreabpqstcfdmlkcfkhriuwkqfcodelppbuxxqxpanwsewtrnccauewokmqqahhykfsawtiatqczizqtmabdxqotpzhufebenhmnmbkavtbaqkpjloblntpbjhazyjtkakpeydymjnhgfsojzzucjvehkuvnefhkytpaasskzteisyylpukgkerhneqjqjkkqkigljadrneojmeyebyissomxlopckhtqz...
result:
ok single line: 'bqrjaovelwrainyujustjcnoyqpyeu...ulctwnloovccolzzlgjbonxkmtsflyq'
Test #10:
score: 0
Accepted
time: 69ms
memory: 80240kb
input:
1 1000 655 xrivmcvikmllrgissoqginwxkoqyxywrvspoagwvuycscxxldlmrszeuiiqzbcvkyvcogtqagprfubjza xrivmcvikmllrgissoqginwxkoqyxwsgqbhhyygxeboxmuseokzosgqwekpchzsatkqlfiffshydwxtetdvwksuotvzaeosixlrlnoqdidbtocqkfwinselyycwpyxwywucccqorepmqsrncceebgbtygqrtviddhsqzpxauobucvondytzflgphhqgxkyaoihvvrqrvkbbleyn...
output:
xrivmcvikmllrgissoqginwxkoqyxwsgqbhhyygxeboxmuseokzosgqwekpchzsatkqlfiffshydwxtetdvwksuotvzaeosixlrlnoqdidbtocqkfwinselyycwpyxwywucccqorepmqsrncceebgbtwiulbxpgqmqazceacggpluxdaxnjcrvcfxzthnkvjegomnbsmbfksetqxuxukwooizgrmgupxlnspeovfiuqyndkkgrzjwxxvpjopmjhknuavonvknpcxwlcjnvrdrvvqxinzktygkkjdhdoewkwx...
result:
ok single line: 'xrivmcvikmllrgissoqginwxkoqyxw...vsirnpcffpggcsscctonqrzhktybdfd'
Test #11:
score: 0
Accepted
time: 84ms
memory: 83860kb
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: 143ms
memory: 151040kb
input:
1 15 3 accbbabccbbbaacaaabaacbacccbabaacbcbbaacbcabcbcabbbaabbbacaccbcacacbacbbbccbacaaabbaacbacbaacbcbbaaccbcbccbaabcbaacaccbbbccbbbccccbbcacacabaabccacccbcabacbbbbacbcaaababbbaacaababccbcacabcbaacccaaabbbcbcbcaaacabaacaabacbcbbccaabaccbbcbabcbcbabaabbbbabbcaacacbbcbabbabccabcbbbcbbbbcbaabcbcbacaba...
output:
EMPTY
result:
ok single line: 'EMPTY'
Test #13:
score: 0
Accepted
time: 53ms
memory: 20292kb
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: 126ms
memory: 142308kb
input:
1 8 2 aljyvnpjccrahfrixfoayvhxhwovfhsrjubibgwlxyhoryqxqlqbbpmszyogtslzmddmwkzwhjvnazabmzqeridgsukgosptmmbemzdfaezqiqedslcjkrlhjikiyzymeulnzxpnhhpbqnbdoqybnsbhesbgqbwfwyuggfnmeiceupezyjtzxhfspwrxnynxbeizewzejejkdfenecqhymgrvdgehzvahevwasmuboqwvblgbahyykskhiqtegqqylhknpbxxspyupyjufonsatqroxunkzenqoagq...
output:
EMPTY
result:
ok single line: 'EMPTY'
Test #15:
score: 0
Accepted
time: 120ms
memory: 145768kb
input:
1 10 5 badcbbacebabaaaaedeebfddecfcdfaccdeccdaffeaddafebdbedacabebbdacffdfeefebaabcbcafafbedacfbcadacfbeabafbeafdeacbdcfafcdfbbacbcbcbedecaedffceeccdfccdebaeeabfccbfdbebacfcebcebfafcfefaddfcacadccdfcfcefebbecdebadabffffecfcdababaddeeddfeccbbffdfabddaedeebcacbadbaadfaebaaaeecadfadbdadcdbdbbcbbfdeacdf...
output:
EMPTY
result:
ok single line: 'EMPTY'
Test #16:
score: 0
Accepted
time: 91ms
memory: 101492kb
input:
1 1005 796 fcfacbaaedfebebafefcaddfcbdeaeadcefdcebaabefbcfcaeddeebabaacbabdadaacfdaafdeebccfcbbffbecebfaaebdbbbbfcdadacfdababacaaacfdfcbdfeefeffbffadffcbbedfebdeefdeeeedcebeaecdbccdecdaefcfaccbabcaebdddffefeedeeafebaceafcdbadeaddcdfeaddafaaeccddbadefadafeebeccbfbceffaaddfbbbacfdacbeadcbeedcdfbecdfab...
output:
fbdfcffefdfefdabbbaaabbbdadbaecbbbfdaeaaefadaaeaacdaeecacfeccccddbedfdacaacdbdcdcaacecbbaabdccadfafdbdbdadbebfaafaeaaaacdecefdecefccacedeabcceabcfbcdeefbcabeddaeedbdaedacbeebaccbefddcdfcbaeaddfdfadadfadcbebccfbbbdbadcecfaceeefcfaebdedebdefdfaeefcedcffaeebcecbffacdcfcefefadaafbfdbadecefbfbfdceebbfcaff
result:
ok single line: 'fbdfcffefdfefdabbbaaabbbdadbae...fadaafbfdbadecefbfbfdceebbfcaff'
Test #17:
score: 0
Accepted
time: 96ms
memory: 101360kb
input:
1 1005 23 ecdafdebadceaebcadfaddbadfcbffbfaafdefecbfbceefaeeccabdaefefddfdccbcbeaeeefdedbadfcacedfabefeabcfdfcfadddadfeeeefcfeedcdcffeaedaffcdabecaecacaebddeaabcaabcebffeecafccdadacbbecbefedeefbebddcbadfdffdfabacddcdefeebddaddfdebafeffdeecaaedafebaceedfacadcdfcbdeafaaeeefcedcfdebfcbaddbdaefceaeafdca...
output:
adbcdacebaebdabbecbfdaebffefcfeaeafdaefefcffcbeeafaeebcfeddfaaaeecbabdbebeeaffebaebbfeeeafbfbfcacbdabbcafcecadbdcdccdddabaeeaacbcdfcbddbccdcaeaeeedcfefacddcbffcefbedabddddfaaffabffcbdbeafaceaaaadabeebbdedcbcbaceffcfdcfafbaeedaabcfabecfecacecdffccbaefabebceedcaadabcfbdbaeabfdccbbbeacefedbbcfbedfddbefae
result:
ok single line: 'adbcdacebaebdabbecbfdaebffefcf...abfdccbbbeacefedbbcfbedfddbefae'
Test #18:
score: 0
Accepted
time: 83ms
memory: 106392kb
input:
1 7 2 bebadebdcebccacabcabeebeebddebcaeceeebeeeadcaccecbccbeecbacbabbedcebdecebaacbedecdbdadcdbeacbabacbdaccbeacaaedeecbadecdabcaaeeecceebeaddbedeeeedbabbdebeddaabcaeeeaeeaeedcbbbbbdabbbdebaaaedaedcbabdceadcdbaaabdecdeabcbbdcbdaceacaddabbedbcadaeaeeedaaedcbeeebebcbceabecdbbcebadadcecddbbdeecbcdbedbb...
output:
EMPTY
result:
ok single line: 'EMPTY'