#include <bits/stdc++.h>
using namespace std;
struct node {
int level;
bool is_marked;
node *son[26];
node() {
level = is_marked = 0;
for (int i = 0; i < 26; ++i)
son[i] = nullptr;
}
};
string s;
int longest;
bool found;
vector<char> sol;
void max_self(int &x, int y) {
x = max(x, y);
}
void Insert(node *nod, int p) {
max_self(longest, nod->level);
if (p == (int)s.size())
return;
int nxt = s[p] - 'a';
if (nod->son[nxt] == nullptr) {
nod->son[nxt] = new node;
nod->son[nxt]->level = nod->level + 1;
}
Insert(nod->son[nxt], p + 1);
}
bool mark(node *nod) {
bool is_leaf = true;
for (int i = 0; i < 26 && is_leaf; ++i)
if (nod->son[i] != nullptr)
is_leaf = false;
if (is_leaf) {
if (found)
return false;
if (nod->level == longest) {
nod->is_marked = true;
found = true;
return true;
}
return false;
}
bool ans = false;
for (int i = 0; i < 26; ++i)
if (nod->son[i] != nullptr)
ans |= mark(nod->son[i]);
if (ans)
nod->is_marked = true;
return ans;
}
void solve(node *nod) {
bool is_leaf = true;
for (int i = 0; i < 26; ++i) {
if (nod->son[i] != nullptr) {
is_leaf = false;
if (nod->son[i]->is_marked == false) {
sol.emplace_back('a' + i);
solve(nod->son[i]);
sol.emplace_back('-');
}
}
}
if (is_leaf) {
sol.emplace_back('P');
return;
}
for (int i = 0; i < 26; ++i) {
if (nod->son[i] != nullptr && nod->son[i]->is_marked) {
sol.emplace_back('a' + i);
solve(nod->son[i]);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
node* root = new node;
for (int i = 0; i < n; ++i) {
cin >> s;
Insert(root, 0);
}
mark(root);
solve(root);
cout << sol.size() << '\n';
for (auto it : sol)
cout << it << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
312 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
332 KB |
didn't print every word |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Incorrect |
1 ms |
204 KB |
didn't print every word |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
332 KB |
didn't print every word |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
1868 KB |
didn't print every word |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
14 ms |
5908 KB |
didn't print every word |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
31 ms |
14688 KB |
didn't print every word |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
78 ms |
36676 KB |
didn't print every word |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
65 ms |
28680 KB |
didn't print every word |
2 |
Halted |
0 ms |
0 KB |
- |