// Problem: Word Combinations
// Contest: CSES - CSES Problem Set
// URL: https://cses.fi/problemset/task/1731/
// Memory Limit: 512 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N = 1e6+5, MOD = 1e9+7;;
int trie[N][31], flag[N], dp[N];
int cont = 1;
vector<char>ans;
void insert(string s)
{
int node = 0;
for(auto it:s)
{
if(trie[node][it-'a'] == 0) trie[node][it-'a'] = cont++;
node = trie[node][it-'a'];
}
flag[node] = true;
}
void dfs(int node)
{
if(flag[node]) ans.push_back('P');
for(int i= 0; i < 26; i++)
{
if(trie[node][i] != 0)
{
ans.push_back(char(i+'a'));
dfs(trie[node][i]);
ans.push_back('-');
}
}
}
signed main()
{
int n;
cin >> n;
for(int i = 0; i < n; i++)
{
string t;
cin >> t;
insert(t);
}
dfs(0);
int cnt = 0, xx = -1, mx = 0, idx = 0;
for(auto it:ans)
{
xx++;
if(it == '-') cnt++;
else
{
cnt = 0;
}
if(cnt > mx) mx = cnt, idx = xx;
}
cout << ans.size()-mx << "\n";
for(int i = idx+1; i < ans.size(); i++) cout << ans[i] << "\n";
bool f= false;
vector<char>pk;
for(int i = idx; i >= 0; i--)
{
if(ans[i] != '-') f = true;
if(f) pk.push_back(ans[i]);
}
for(int i = pk.size()-1; i >= 0; i--)
{
cout << pk[i] << "\n";
}
return 0;
}
# | 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... |