#include <bits/stdc++.h>
using namespace std;
void fast(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
struct trie{
int val; bool word;
trie *ch[26];
trie(){
val=0, word=0;
for(int i=0; i<26; i++) ch[i]=NULL;
}
}root;
void add(string &s){
trie *now=&root;
for(int i=0; i<(int)s.size(); i++){
if(!now->ch[s[i]-'a']) now->ch[s[i]-'a']=new trie();
now=now->ch[s[i]-'a'];
}
now->word=1;
}
void dfs(trie *now){
trie *next;
for(int i=0; i<26; i++){
if(now->ch[i]){
next=now->ch[i];
dfs(next);
now->val=max(now->val, next->val);
}
}
now->val++;
}
vector<char> v;
void dfs2(trie *now){
trie *next;
int c=27, maxn=0;
if(now->word) v.push_back('P');
for(int i=0; i<26; i++){
if(now->ch[i]){
next=now->ch[i];
if(next->val>maxn){
maxn=next->val;
c=i;
}
}
}
for(int i=0; i<26; i++){
if(now->ch[i] && i!=c){
v.push_back(char('a'+i));
dfs2(now->ch[i]);
}
}
if(maxn){
v.push_back(char('a'+c));
dfs2(now->ch[c]);
}
v.push_back('-');
}
int main(){
fast();
int n; cin>>n;
for(int i=1; i<=n; i++){
string s; cin>>s; add(s);
}
dfs(&root);
dfs2(&root);
while(!v.empty() && v.back()=='-') v.pop_back();
cout<<v.size()<<'\n';
for(auto i:v) cout<<i<<'\n';
}
/*
struct trie{
trie *ch[26];
trie(){
for(int i=0; i<26; i++) ch[i]=NULL;
}
}root[2];
void add(string &s, int k){
trie *now=&root[k];
for(int i=0; i<(int)s.size(); i++){
if(!now->ch[s[i]-'a']) now->ch[s[i]-'a']=new trie();
now=now->ch[s[i]-'a'];
}
}
bool dfs(trie *a, trie *b, int k){
bool ans;
if(k&1){
ans=0;
for(int i=0; i<26; i++){
if(a->ch[i] && b->ch[i]) ans|=dfs(a->ch[i], b->ch[i], k+1);
else if(a->ch[i]){
ans=1;
break;
}
}
}
else{
ans=1;
for(int i=0; i<26; i++){
if(a->ch[i] && b->ch[i]) ans&=dfs(a->ch[i], b->ch[i], k+1);
else if(b->ch[i]){
ans=0;
break;
}
}
}
return ans;
}
int main(){
fast();
int n; cin>>n;
for(int i=1; i<=n; i++){
string s; cin>>s; add(s, 0);
}
int m; cin>>m;
for(int i=1; i<=m; i++){
string s; cin>>s; add(s, 1);
}
if(dfs(&root[0], &root[1], 1)) cout<<"Nina";
else cout<<"Emilija";
}
*/
/*
struct trie{
bool val;
trie *ch[26];
trie(){
val=0;
for(int i=0; i<26; i++) ch[i]=NULL;
}
}root;
void add(string &s){
trie *now=&root;
for(int i=0; i<(int)s.size(); i++){
if(!now->ch[s[i]-'a']) now->ch[s[i]-'a']=new trie();
now=now->ch[s[i]-'a'];
}
now->val=1;
}
int main(){
fast();
int n, m; cin>>n>>m;
string s; cin>>s;
for(int i=1; i<=m; i++){
string t; cin>>t; add(t);
}
string t="";
int ans=0;
trie *now=&root;
for(int i=0; i<n; i++){
if(!now->ch[s[i]-'a']){
t.clear();
now=&root;
}
if(now->ch[s[i]-'a']){
now=now->ch[s[i]-'a'];
if(now->val){
ans++;
t.clear();
now=&root;
}
else t+=s[i];
}
}
cout<<ans;
}
*/
/*
#define int long long
const int N=5e3, NN=1e6, mod=1e9+7;
int dp[N+1];
struct trie{
bool val;
trie *ch[26];
trie(){
val=0;
for(int i=0; i<26; i++) ch[i]=NULL;
}
}root;
void add(string &s){
trie *now=&root;
for(int i=(int)s.size()-1; i>=0; i--){
if(!now->ch[s[i]-'a']) now->ch[s[i]-'a']=new trie();
now=now->ch[s[i]-'a'];
}
now->val=1;
}
vector<int> v;
void f(string &s){
trie *now=&root;
for(int i=(int)s.size()-1; i>=0; i--){
int c=s[i]-'a';
if(!now->ch[c]) return;
now=now->ch[c];
if(now->val) v.push_back(i);
}
}
// int now=1, trie[NN+1][26], exi[NN+1], word[NN+1];
// void add(string &s){
// int id=0;
// for(int i=s.size()-1; i>=0; i--){
// if(!exi[trie[id][s[i]-'a']]){
// trie[id][s[i]-'a']=now++;
// exi[now-1]=1;
// }
// id=trie[id][s[i]-'a'];
// }
// word[id]=1;
// }
// vector<int> v;
// void f(string &s){
// int id=0;
// for(int i=s.size()-1; i>=0; i--){
// if(!exi[trie[id][s[i]-'a']]) return;
// id=trie[id][s[i]-'a'];
// if(word[id]) v.push_back(i);
// }
// }
signed main(){
fast();
string s; cin>>s;
int n=(int)s.size(), k; cin>>k;
for(int i=1; i<=k; i++){
string t; cin>>t; add(t);
}
string t="";
dp[0]=1;
for(int i=1; i<=n; i++){
t+=s[i-1];
v.clear();
f(t);
for(auto j:v) dp[i]+=dp[j];
dp[i]%=mod;
}
cout<<dp[n];
//for(int i=0; i<=n; i++) cout<<dp[i]<<' ';
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1884 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
6104 KB |
Output is correct |
| 2 |
Correct |
17 ms |
12636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
14808 KB |
Output is correct |
| 2 |
Correct |
6 ms |
3416 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
36572 KB |
Output is correct |
| 2 |
Correct |
114 ms |
83652 KB |
Output is correct |
| 3 |
Correct |
61 ms |
43152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
28624 KB |
Output is correct |
| 2 |
Correct |
144 ms |
99708 KB |
Output is correct |
| 3 |
Correct |
69 ms |
48992 KB |
Output is correct |
| 4 |
Correct |
119 ms |
94148 KB |
Output is correct |
