#include "bits/stdc++.h"
/*
* Author: Matheus Monteiro
*/
using namespace std;
#define _ << " , " <<
#define bug(x) cout << #x << " >>>>>>> " << x << endl;
// #define int long long
#define Max(a, b) (a > b ? a : b)
#define Min(a, b) (a < b ? a : b)
#define ii pair<int, int>
#define f first
#define s second
#define vi vector<int>
#define vii vector<ii>
#define LSOne(S) ((S) & (-S))
#define UNTIL(t) while (clock() < (t) * CLOCKS_PER_SEC)
#define SZ(a) (int)a.size()
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int MAX = 600010; //2 * 10^5
const int MOD = 1000000007; //10^9 + 7
const int OO = 0x3f3f3f3f; // 0x3f3f3f3f;
const double EPS = 1e-9; //10^-9
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int trie[MAX][26], next_vertex = 1, n;
int h[MAX], sc[MAX];
bool leaf[MAX];
void add(string &s) {
int r = 0;
for(char &c : s) {
if(!trie[r][c - 'a']) trie[r][c - 'a'] = next_vertex++;
r = trie[r][c - 'a'];
}
leaf[r] = true;
}
int go(int node, int i) {
return trie[node][i];
}
void dfs_sz(int u) {
h[u] = 1;
for(int i = 0; i < 26; ++i) {
int v = go(u, i);
if(v) {
dfs_sz(v);
if(sc[u] == -1) sc[u] = v;
h[u] = max(h[v] + 1, h[u]);
if(h[sc[u]] < h[v]) sc[u] = v;
}
}
}
string ans;
void dfs(int r) {
if(leaf[r]) ans.push_back('P');
char c;
for(int i = 0; i < 26; ++i) {
int v = go(r, i);
if(v == sc[r]) {
c = char(i + 'a');
continue;
}
if(v) {
ans.push_back(char(i + 'a'));
dfs(v);
ans.push_back('-');
}
}
if(sc[r] > 0) {
ans.push_back(c);
dfs(sc[r]);
ans.push_back('-');
}
}
void solve() {
cin >> n;
for(int i = 0; i < n; ++i) {
string s;
cin >> s;
add(s);
}
memset(sc, -1, sizeof(sc));
dfs_sz(0);
dfs(0);
while(ans.back() == '-') ans.pop_back();
cout << SZ(ans) << '\n';
for(char c : ans)
cout << c << '\n';
}
int32_t main() {
fastio;
int t = 1;
//cin >> t;
for(int caso = 1; caso <= t; ++caso) {
//cout << "Case #" << caso << ": ";
solve();
}
return 0;
}
/*
Before submit:
Check the corners cases
Check solution restrictions
For implementation solutions:
Check the flow of the variables
For intervals problems:
Think about two pointers
For complete search:
Think about cuts
If you get WA:
Reread your code looking for stupid typos
Try various manual testcases
Recheck the correctness of your algorithm
Reread the statement
Write a straightforward solution, create lots of testcases by yourself, and compare both solutions
Generate random test cases and perform a stress test, comparing your solution with the one that you are sure is correct
Change the coder (if you're with a team)
Give up. You may have other tasks to solve.
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3404 KB |
Output is correct |
| 2 |
Correct |
4 ms |
3660 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
5540 KB |
Output is correct |
| 2 |
Correct |
18 ms |
8860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
9912 KB |
Output is correct |
| 2 |
Correct |
9 ms |
4172 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
20832 KB |
Output is correct |
| 2 |
Correct |
97 ms |
44192 KB |
Output is correct |
| 3 |
Correct |
55 ms |
24448 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
16868 KB |
Output is correct |
| 2 |
Correct |
117 ms |
52224 KB |
Output is correct |
| 3 |
Correct |
62 ms |
27344 KB |
Output is correct |
| 4 |
Correct |
100 ms |
49792 KB |
Output is correct |
