#include<bits/stdc++.h>
using namespace std;
#define ShIbAiNu_LoVe_CaPpUcCiNo ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
/*From OpenGenus*/
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
//mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());
//#define SHUF(v) shuffle(all(v), RNG);
// Use mt19937_64 for 64 bit random numbers.
typedef long long ll;
typedef unsigned long long ull;
typedef long int int32;
typedef unsigned long int uint32;
typedef long long int int64;
typedef unsigned long long int uint64;
#define int long long
#define WON(i,a,b) for(int i = (int)a; i<=(int)b; i++)
#define NOW(i,a,b) for(int i = (int)a; i>=(int)b; i--)
#define REP(i, n) for(int i = 0; i <= (int)n; i++)
#define PER(i, n) for(int i = (int)n; i>=0; i--)
#define TRAV(a, x) for (auto& a : x)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define PI 3.1415926535897932384626
#define sqr(x) (x) * (x)
#define bit(x, i) (((x) >> (i)) & 1)
#define ar array
#define ld long double
#define sza(x) ((int)x.size())
#define all(a) (a).begin(), (a).end()
#define taskname "test"
#define frein freopen(taskname".INP","r",stdin)
#define freou freopen(taskname".OUT","w",stdout)
const int MAX_N = 1e6 + 5;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ld EPS = 1e-9;
void firstWord() {
cout << "Drink a cup of Cappuccino before reading Shiba's cute code ^_^";
}
class Trie {
private:
struct TrieNode {
unordered_map<char, TrieNode*> children;
bool endOfWord;
bool l;
TrieNode() : endOfWord(false), l(false) {}
};
TrieNode* root;
string ans;
public:
Trie() {
root = new TrieNode();
}
void insert(const string &word, bool p) {
TrieNode* current = root;
for (char ch : word) {
if (current->children.find(ch) == current->children.end()) {
current->children[ch] = new TrieNode();
}
current = current->children[ch];
current->l = p;
}
current->endOfWord = true;
current->l = p;
}
void traverse() {
ans.clear();
traverseHelper(root);
}
void printAns() {
cout << ans.size() << "\n";
for (char ch : ans) {
cout << ch << "\n";
}
}
private:
void traverseHelper(TrieNode* node) {
if (node->endOfWord) {
ans += "P";
}
int pending = -1;
TrieNode* childNode;
for (auto &child : node->children) {
int ch = child.first - 'a';
childNode = child.second;
if (childNode->l) {
pending = ch;
continue;
}
ans.push_back(child.first);
traverseHelper(childNode);
ans += "-";
}
if (pending != -1) {
ans.push_back('a' + pending);
traverseHelper(node->children['a' + pending]);
}
}
};
void shibaSolve() {
int n;
cin >> n;
string word, larger;
int maxi = 0;
Trie trie;
for (int i = 1; i <= n; i++) {
cin >> word;
trie.insert(word, false);
if (word.size() > maxi) {
maxi = word.size();
larger = word;
}
}
trie.insert(larger, true);
trie.traverse();
trie.printAns();
}
void shibaSecretMessage() {
cout << "Such code, much WoW ^^!";
}
signed main() {
ShIbAiNu_LoVe_CaPpUcCiNo
//frein;
//freou;
//firstWord();
ll t = 1;
//cin>>t;
while(t--) {shibaSolve();}
//shibaSecretMessage();
return 0;
}
Compilation message
printer.cpp: In function 'void shibaSolve()':
printer.cpp:136:25: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
136 | if (word.size() > maxi) {
| ~~~~~~~~~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1880 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2120 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
5724 KB |
Output is correct |
| 2 |
Correct |
17 ms |
11868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
13800 KB |
Output is correct |
| 2 |
Correct |
8 ms |
3164 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
34832 KB |
Output is correct |
| 2 |
Correct |
153 ms |
81156 KB |
Output is correct |
| 3 |
Correct |
86 ms |
40568 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
26100 KB |
Output is correct |
| 2 |
Correct |
119 ms |
96524 KB |
Output is correct |
| 3 |
Correct |
87 ms |
46064 KB |
Output is correct |
| 4 |
Correct |
160 ms |
90828 KB |
Output is correct |
