#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;
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)) {
cout << "P\n";
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;}
cout << (char)('a' + x) << '\n';
dfs(t[v][x], lasts);
}
}
if (i != -1) {
cout << (char)('a' + i) << '\n';
lasts.pop_back();
dfs(t[v][i], lasts);
}
if (en.size())
cout << "-\n";
}
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);
return 0;
}
Compilation message
printer.cpp: In function 'void add(std::string&)':
printer.cpp:25:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for (int i = 0; i < s.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
300 KB |
Expected integer, but "t" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
296 KB |
Expected integer, but "e" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Expected integer, but "h" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
300 KB |
Expected integer, but "b" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
300 KB |
Expected integer, but "a" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1100 KB |
Expected integer, but "a" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
3376 KB |
Expected integer, but "a" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
8480 KB |
Expected integer, but "a" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
100 ms |
20676 KB |
Expected integer, but "b" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
80 ms |
16764 KB |
Expected integer, but "b" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
