#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using indexed_set = tree<T, null_type, less<T>,
rb_tree_tag, tree_order_statistics_node_update>;
#define watch(x) cerr << "{" << (#x) << " = " << x << "}" << '\n';
#define watch2(x, y) cerr << "{" << (#x) << " = " << x << ", " << (#y) << " = " << y << "}" << '\n';
#define watch3(x, y, z) cerr << "{" << (#x) << " = " << x << ", " << (#y) << " = " << y << ", " << (#z) << " = " << z << "}" << '\n';
#define fast_io ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
const ll maxn = 2e5 + 10;
int n, t[maxn][30], nodes = 1;
set<int> en;
vector<char> ans;
void add (string &s)
{
int v = 0;
for (int i = 0; i < s.size(); i++) {
if (!t[v][s[i] - 'a']) t[v][s[i] - 'a'] = nodes++;
v = t[v][s[i] - 'a'];
}
en.insert(v);
}
void dfs (int v, vector<int> lasts)
{
if (en.count(v)) {
ans.push_back('P');
en.erase(v);
}
int i = -1;
for (int x = 0; x < 27; x++) {
if (t[v][x]) {
if (t[v][x] == lasts.back()) {i = x; continue;}
ans.push_back((char)('a' + x));
dfs(t[v][x], lasts);
}
}
if (i != -1) {
ans.push_back((char)('a' + i));
lasts.pop_back();
dfs(t[v][i], lasts);
}
if (en.size())
ans.push_back('-');
}
pair<string, vector<int>> dfs2 (int v, string s, vector<int> ss)
{
int degree = 0;
for (int x = 0; x < 27; x++) {
if (t[v][x]) degree++;
}
if (degree > 1) s = "";
string res = s;
vector<int> res2 = ss;
for (int x = 0; x < 27; x++) {
if (t[v][x]) {
s += (char)('a' + x);
ss.push_back(t[v][x]);
auto p = dfs2(t[v][x], s, ss);
s.pop_back();
ss.pop_back();
if (res.size() < p.first.size()) {
res = p.first;
res2 = p.second;
}
}
}
return {res, res2};
}
int main ()
{
cin >> n;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
add(s);
}
auto p = dfs2(0, "", {});
reverse(p.second.begin(), p.second.end());
dfs(0, p.second);
cout << ans.size() << '\n';
for (char c : ans)
cout << c << '\n';
return 0;
}
Compilation message
printer.cpp: In function 'void add(std::string&)':
printer.cpp:26:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | for (int i = 0; i < s.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
300 KB |
Output is correct |
| # |
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 |
204 KB |
Output is correct |
| # |
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 |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
2 ms |
716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
1100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
3472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
8640 KB |
Output is correct |
| 2 |
Correct |
18 ms |
2628 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
101 ms |
21036 KB |
Output is correct |
| 2 |
Runtime error |
54 ms |
49344 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
90 ms |
16940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
