#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define rall(x) x.rbegin(), x.rend()
//#define int long long
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;
const double eps = 1e-9;
void setIO() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
struct Node {
bool isWord;
int chars;
map<char, Node*> child;
Node() : isWord(false), chars(0) {}
};
bool cmp(pair<Node*, char> a, pair<Node*, char> b) {
return a.first->chars < b.first->chars;
}
struct Trie {
Node* root;
int totalWords;
string dfsAns;
int totalOp;
int foundSoFar;
Trie() {
root = new Node();
totalWords = 0;
dfsAns = "";
totalOp = 0;
}
~Trie() {
delete root;
}
void insert(string &word) {
Node* curr = root;
int added = 0;
for(char &ch : word) {
if(!curr->child.count(ch))
curr->child[ch] = new Node();
curr = curr->child[ch];
curr->chars = max(curr->chars, sz(word) - added);
added++;
}
curr->isWord = true;
totalWords++;
}
void dfs(Node* curr, char ch) {
if(ch != ' ') dfsAns += ch, totalOp++;
if(curr->isWord == true) dfsAns += 'P', totalOp++, foundSoFar++;
vector<pair<Node*, char> > nextVec;
for(auto &next : curr->child)
nextVec.push_back({ next.second, next.first });
sort(all(nextVec), cmp);
for(auto &next : nextVec)
dfs(next.first, next.second);
if(ch != ' ' && foundSoFar < totalWords) dfsAns += '-', totalOp++;
}
void callDFS() {
foundSoFar = 0;
dfs(root, ' ');
cout << totalOp << '\n';
for(char &ch : dfsAns)
cout << ch << '\n';
}
};
int32_t main() {
setIO();
int n;
cin >> n;
Trie trie;
for(int i=0; i<n; i++) {
string s;
cin >> s;
trie.insert(s);
}
trie.callDFS();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1108 KB |
Output is correct |
2 |
Correct |
3 ms |
1492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
3640 KB |
Output is correct |
2 |
Correct |
13 ms |
7456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
8680 KB |
Output is correct |
2 |
Correct |
7 ms |
2236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
21376 KB |
Output is correct |
2 |
Correct |
99 ms |
49200 KB |
Output is correct |
3 |
Correct |
51 ms |
25468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
16744 KB |
Output is correct |
2 |
Correct |
109 ms |
58500 KB |
Output is correct |
3 |
Correct |
61 ms |
28928 KB |
Output is correct |
4 |
Correct |
98 ms |
55252 KB |
Output is correct |