This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
struct Node{
Node* c[26];
int maxdepth=0;
bool leaf=false;
Node(){
for(int i=0;i<26;i++) c[i]=nullptr;
}
};
Node* root=new Node();
void insert(string s){
Node* node=root;
int n=s.length();
for(int i=0;i<n;i++){
if(node->c[s[i]-'a']==nullptr) node->c[s[i]-'a']=new Node();
node=node->c[s[i]-'a'];
node->maxdepth=max(node->maxdepth,n);
}
node->leaf=true;
}
int k;
vector<char> op;
void dfs(Node* node){
int best=-1;
int mx=-1;
for(int i=0;i<26;i++){
if(node->c[i]!=nullptr){
if(node->c[i]->maxdepth>mx){
mx=node->c[i]->maxdepth;
best=i;
}
}
}
if(node->leaf){
k--;
op.push_back('P');
}
for(int j=0;j<26;j++){
if(node->c[j]){
if(j==best) continue;
op.push_back(char('a'+j));
dfs(node->c[j]);
if(k!=0)
op.push_back('-');
}
}
if(best!=-1){
op.push_back(char(best+'a'));
dfs(node->c[best]);
if(k!=0) op.push_back('-');
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n;
cin>>n;
k=n;
string s;
for(int i=0;i<n;i++){
cin>>s;
insert(s);
}
dfs(root);
cout<<op.size()<<"\n";
for(auto x:op){
cout<<x<<"\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |