#include <bits/stdc++.h>
using namespace std;
struct node {
node *child[26];
int sub;
bool isEnd = false;
};
node *make() {
node *u = new node;
for (int i = 0; i < 26; i++) {
u->child[i] = nullptr;
}
u->sub = 0;
u->isEnd = false;
return u;
}
void insert(node *root, string s) {
node *u = root;
for (char c : s) {
int idx = c - 'a';
if (u->child[idx] == nullptr) {
u->child[idx] = make();
}
u = u->child[idx];
}
u->isEnd = true;
}
void dfs(node *root) {
node *u = root;
u->sub = 1;
for (int i = 0; i < 26; i++) {
if (u->child[i] != nullptr) {
dfs(u->child[i]);
u->sub += u->child[i]->sub;
}
}
}
vector<char> op;
void go(node *root) {
node *u = root;
if (u->isEnd) op.push_back('P');
vector<int> ord;
for (int i = 0; i < 26; i++) {
if (u->child[i] == nullptr) continue;
ord.push_back(i);
}
sort(ord.begin(), ord.end(), [&] (int i, int j) {
return u->child[i]->sub < u->child[j]->sub;
});
int cnt = 1;
for (int i : ord) {
op.push_back(i + 'a');
++cnt;
go(u->child[i]);
}
op.push_back('-');
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
node *root = make();
int n;
cin >> n;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
insert(root, s);
}
dfs(root);
go(root);
while (op.back() == '-') op.pop_back();
for (char c : op) {
cout << c << '\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
384 KB |
Expected integer, but "t" found |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
384 KB |
Expected integer, but "n" found |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
384 KB |
Expected integer, but "h" found |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
384 KB |
Expected integer, but "q" found |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
512 KB |
Expected integer, but "w" found |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
7 ms |
1920 KB |
Expected integer, but "u" found |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
17 ms |
6016 KB |
Expected integer, but "k" found |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
54 ms |
14808 KB |
Expected integer, but "j" found |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
84 ms |
36724 KB |
Expected integer, but "s" found |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
88 ms |
28788 KB |
Expected integer, but "m" found |
2 |
Halted |
0 ms |
0 KB |
- |