QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #417818 | #6516. New but Nostalgic Problem | wxgmjfhy | TL | 6ms | 23876kb | C++17 | 1.0kb | 2024-05-22 22:39:20 | 2024-05-22 22:39:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int nex[N][26],cnt;
int num[N][26];
int n,k;
inline void insert(string s){
int p=0;
for(auto w:s){
int c=w-'a';
if(!nex[p][c])nex[p][c]=++cnt;
num[p][c]++;
p=nex[p][c];
}
}
inline string get(string s){
int p=0;
string t="";
for(auto w:s){
int c=w-'a';
if(num[p][c]<=1)return t;
t+=w;
p=nex[p][c];
}
return t;
}
inline void solve(){
memset(nex,0,sizeof nex);
memset(num,0,sizeof num);
cnt=0;
cin>>n>>k;
vector<string>a(n);
for(int i=0;i<n;i++){
cin>>a[i];
insert(a[i]);
}
sort(a.begin(),a.end());
for(auto w:a){
string ans=get(w);
if(ans!=""){
cout<<ans<<"\n";
return;
}
}
cout<<"EMPTY\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int _=1;
cin>>_;
while(_--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 6ms
memory: 23876kb
input:
2 5 3 gdcpc gdcpcpcp suasua suas sususua 3 3 a b c
output:
gdcpc EMPTY
result:
ok 2 lines
Test #2:
score: -100
Time Limit Exceeded
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 t EMPTY EMPTY m EMPTY a EMPTY EMPTY EMPTY EMPTY EMPTY e r EMPTY o v EMPTY w EMPTY EMPTY t EMPTY s z v EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY w EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY w u EMPTY EMPTY EMPTY EMPTY EMPTY EMPTY EMPT...