QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #141236 | #6516. New but Nostalgic Problem | cy1999 | WA | 143ms | 13884kb | C++20 | 1.2kb | 2023-08-17 09:55:13 | 2023-08-17 09:55:40 |
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);
nw++;
}
}
if(fc[x]+rt+sks[x]>=k)res=x;
}
int main(){
cin>>t;
while(t--){
res=-1;
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);
if(res==-1)return -1;
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: 2ms
memory: 13748kb
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: 143ms
memory: 13848kb
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: 88ms
memory: 13884kb
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: -100
Wrong Answer
time: 129ms
memory: 13824kb
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:
wrong answer 3236th lines differ - expected: 'pfv', found: 'u'