#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
struct node {
node *child[26];
char mx;
bool leaf;
} rt;
void add(string s)
{
node *t = &rt;
for (char c : s) {
c -= 'a';
if (!t->child[c])
t->child[c] = new node;
t = t->child[c];
}
t->leaf = 1;
}
vector<char> ans;
int dfs1(node *t, int h)
{
int mx = h;
Loop (i,0,26) {
if (t->child[i]) {
int x = dfs1(t->child[i], h+1);
if (x > mx) {
mx = x;
t->mx = i;
}
}
}
return mx;
}
void dfs2(node *t, bool ret)
{
if (t->leaf)
ans.push_back('P');
Loop (i,0,26) {
if ((ret || i != t->mx) && t->child[i]) {
ans.push_back(i+'a');
dfs2(t->child[i], 1);
ans.push_back('-');
}
}
if (!ret && t->child[t->mx]) {
ans.push_back(t->mx+'a');
dfs2(t->child[t->mx], 0);
}
}
int main()
{
cin.tie(0) -> sync_with_stdio(false);
int n;
cin >> n;
Loop (i,0,n) {
string s;
cin >> s;
add(s);
}
dfs1(&rt, 0);
dfs2(&rt, 0);
cout << ans.size() << '\n';
for (char c : ans)
cout << c << '\n';
}
Compilation message
printer.cpp: In function 'void add(std::string)':
printer.cpp:20:17: warning: array subscript has type 'char' [-Wchar-subscripts]
20 | if (!t->child[c])
| ^
printer.cpp:21:13: warning: array subscript has type 'char' [-Wchar-subscripts]
21 | t->child[c] = new node;
| ^
printer.cpp:22:16: warning: array subscript has type 'char' [-Wchar-subscripts]
22 | t = t->child[c];
| ^
printer.cpp: In function 'void dfs2(node*, bool)':
printer.cpp:53:26: warning: array subscript has type 'char' [-Wchar-subscripts]
53 | if (!ret && t->child[t->mx]) {
| ~~~^~
printer.cpp:55:20: warning: array subscript has type 'char' [-Wchar-subscripts]
55 | dfs2(t->child[t->mx], 0);
| ~~~^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
320 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
320 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
320 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
1108 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
1748 KB |
Output is correct |
2 |
Correct |
4 ms |
2260 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
5992 KB |
Output is correct |
2 |
Correct |
18 ms |
12484 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
30 ms |
14772 KB |
Output is correct |
2 |
Correct |
7 ms |
3412 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
56 ms |
36624 KB |
Output is correct |
2 |
Correct |
118 ms |
83668 KB |
Output is correct |
3 |
Correct |
82 ms |
43188 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
51 ms |
28616 KB |
Output is correct |
2 |
Correct |
142 ms |
99636 KB |
Output is correct |
3 |
Correct |
75 ms |
48952 KB |
Output is correct |
4 |
Correct |
115 ms |
94000 KB |
Output is correct |