#include <bits/stdc++.h>
using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x);
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef DEBUG
#define dbg(x...) cerr <<__func__<<":"<<" [" << #x << "] = ["; _print(x); /*cerr << "\e[39m" << endl;*/
#else
#define dbg(x...)
#endif
#define ll long long
#define ld long double
#define int long long
#define fi first
#define se second
#define pb push_back
#define ii pair<ll,ll>
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define sz(x) (ll)x.size()
#define endl '\n'
const ll N = 25000, INF = 1e18, MOD = 1e9+7;
const int S = 26;
int t = 0;
struct Node {
vector<int> nxt;
bool is_word = 0;
int height = 0;
Node() {
nxt.assign(S, -1);
}
};
//vector<Node> trie(1);
Node trie[N * S];
void add_str(string& s) {
int v = 0;
for (int i = 0; i < sz(s); i++) {
int cur = s[i] - 'a';
if (trie[v].nxt[cur] == -1) {
trie[v].nxt[cur] = ++t;
//trie[v].nxt[cur] = sz(trie);
//trie.emplace_back();
}
v = trie[v].nxt[cur];
trie[v].height = max(trie[v].height, sz(s) - i);
if (i == sz(s) - 1) {
trie[v].is_word = 1;
}
}
}
void solve() {
int n;
cin >> n;
vector<string> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
add_str(a[i]);
}
vector<char> ans;
function<void(int)> dfs = [&] (int v) {
if (trie[v].is_word) ans.emplace_back('P');
int mx = -1, who = -1;
for (int i = 0; i < S; i++) {
int u = trie[v].nxt[i];
if (u == -1) continue;
if (mx < trie[u].height) {
mx = trie[u].height;
who = i;
}
}
//dbg(char('a' + who), mx)
for (int i = 0; i < S; i++) {
int u = trie[v].nxt[i];
if (u == -1 || i == who) continue;
ans.emplace_back(char('a' + i));
dfs(u);
}
if (who != -1) {
ans.emplace_back(char('a' + who));
dfs(trie[v].nxt[who]);
}
ans.emplace_back('-');
};
dfs(0);
while (ans.back() == '-') ans.pop_back();
cout << sz(ans) << endl;
for (int i = 0; i < sz(ans); i++) {
cout << ans[i] << endl;
}
// READ AT THE BOTTOM PLS!
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int tt = 1;
// cin >> tt;
while (tt--) solve();
return 0;
}
/* stuff you should look for
* int overflow, array bounds
* special cases (n = 1?)
* READ CONSTRAINTS
* reset variables?
* STAY ORGANIZED
*/
/*
Suppose I did find such a solution, what would it look like?
What characteristics it would have?
Can we toy around with such a solution so that it remains optimal?
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
168192 KB |
Output is correct |
| 2 |
Correct |
88 ms |
168156 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
168208 KB |
Output is correct |
| 2 |
Correct |
87 ms |
168212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
168108 KB |
Output is correct |
| 2 |
Correct |
87 ms |
168172 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
90 ms |
168212 KB |
Output is correct |
| 2 |
Correct |
95 ms |
168096 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
168136 KB |
Output is correct |
| 2 |
Correct |
88 ms |
168260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
106 ms |
168372 KB |
Output is correct |
| 2 |
Correct |
91 ms |
168268 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
168472 KB |
Output is correct |
| 2 |
Correct |
103 ms |
169052 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
103 ms |
169156 KB |
Output is correct |
| 2 |
Correct |
94 ms |
168976 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
127 ms |
170288 KB |
Output is correct |
| 2 |
Correct |
176 ms |
172612 KB |
Output is correct |
| 3 |
Correct |
139 ms |
171576 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
120 ms |
170040 KB |
Output is correct |
| 2 |
Correct |
197 ms |
173264 KB |
Output is correct |
| 3 |
Correct |
140 ms |
171996 KB |
Output is correct |
| 4 |
Correct |
176 ms |
173228 KB |
Output is correct |
