/*
Khangnh's code
“You can either experience the pain of discipline or the pain of regret.
The choice is yours.”
*/
// - Only when necessary :d
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define fileopen(a, b) freopen(((string)a + ".inp").c_str(), "r", stdin); freopen(((string)b + ".out").c_str(), "w", stdout);
#define ll long long
// #define int long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
typedef pair<int, int> pii;
const ll mod = 1e9 + 7;
const ll inf = 1e9 + 7;
const double eps = 1e-9;
struct node {
int child[26];
int fin;
};
string mx;
vector<char> ans;
struct trie {
int n;
node t[500005];
trie() : n(0) {
memset(t[0].child, -1, sizeof(t[0].child));
t[0].fin = 0;
}
void init(int u) {
memset(t[u].child, -1, sizeof(t[u].child));
t[u].fin = 0;
}
void push(string &s) {
int u = 0;
for (int i = 0; i < s.size(); ++i) {
if (t[u].child[s[i] - 'a'] == -1) {
init(++n);
t[u].child[s[i] - 'a'] = n;
}
u = t[u].child[s[i] - 'a'];
}
++t[u].fin;
}
void dfs(int u, int dep, bool longest) {
if (t[u].fin > 0) ans.pb('P');
int c = mx[dep] - 'a';
for (int i = 0; i < 26; ++i) {
if (i == c && longest) continue;
if (t[u].child[i] != -1) {
ans.pb(char(i + 'a'));
dfs(t[u].child[i], dep + 1, 0);
ans.pb('-');
}
}
if (dep < mx.size() && longest) {
ans.pb(char(c + 'a'));
if (t[u].child[c] != -1) dfs(t[u].child[c], dep + 1, 1);
}
}
} t;
int n;
void solve() {
cin >> n;
for (int i = 1; i <= n; ++i) {
string s;
cin >> s;
t.push(s);
if (mx.size() < s.size()) mx = s;
}
t.dfs(0, 0, 1);
cout << ans.size() << "\n";
for (auto x : ans) cout << x << "\n";
}
signed main() {
#ifdef LOCAL
fileopen("input", "output");
auto start = clock();
#endif
#ifndef LOCAL
// fileopen("LAH", "LAH");
#endif
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int test = 1;
// cin >> test;
for (int tc = 1; tc <= test; ++tc) solve();
#ifdef LOCAL
auto end = clock();
cout << "\n\nExecution time : " << double(end - start)/CLOCKS_PER_SEC << "[s]";
#endif
return 0;
}
Compilation message
printer.cpp: In member function 'void trie::push(std::string&)':
printer.cpp:56:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for (int i = 0; i < s.size(); ++i) {
| ~~^~~~~~~~~~
printer.cpp: In member function 'void trie::dfs(int, int, bool)':
printer.cpp:79:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | if (dep < mx.size() && longest) {
| ~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
2 ms |
716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1228 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
3148 KB |
Output is correct |
| 2 |
Correct |
15 ms |
6456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
7560 KB |
Output is correct |
| 2 |
Correct |
7 ms |
1900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
18492 KB |
Output is correct |
| 2 |
Correct |
89 ms |
41928 KB |
Output is correct |
| 3 |
Correct |
55 ms |
21800 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
14532 KB |
Output is correct |
| 2 |
Correct |
110 ms |
49932 KB |
Output is correct |
| 3 |
Correct |
57 ms |
24768 KB |
Output is correct |
| 4 |
Correct |
95 ms |
47164 KB |
Output is correct |
