/** I can do this all day **/
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#define Mp make_pair
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
const int N = 5e5 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 22;
const int sigma = 26;
ll pw(ll a , ll b, ll M) { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }
char C[N];
int n, ts, node, H[N], End[N], nxt[sigma][N], par[N], mark[N];
string out;
void dfs(int v)
{
if(End[v])
{
out += "P";
}
for(int i = 0; i < sigma; i ++)
{
if(nxt[i][v] == 0 || mark[nxt[i][v]]) continue;
out += string(1, 'a' + i);
dfs(nxt[i][v]);
out += "-";
}
if(mark[v])
{
for(int i = 0; i < sigma; i ++)
{
if(nxt[i][v] && mark[nxt[i][v]])
{
out += string(1, 'a' + i);
dfs(nxt[i][v]);
}
}
}
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++)
{
scanf("%s", C);
string s = C;
int v = 0;
for(int j = 0; j < SZ(s); j ++)
{
int ch = s[j] - 'a';
if(!nxt[ch][v]) nxt[ch][v] = ++ ts;
H[nxt[ch][v]] = H[v] + 1;
par[nxt[ch][v]] = v;
v = nxt[ch][v];
}
End[v] ++;
if(H[v] > H[node]) node = v;
///printf("i = %d H = %d v = %d node = %d\n", i, H[v], v, node);
}
while(node)
{
///printf("marking node = %d\n", node);
mark[node] = 1;
node = par[node];
}
mark[0] = 1;
dfs(0);
printf("%d\n", SZ(out));
for(int i = 0; i < SZ(out); i ++)
{
printf("%c\n", out[i]);
}
return 0;
}
/** test corner cases(n = 1?) watch for overflow or minus indices **/
Compilation message
printer.cpp: In function 'int main()':
printer.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
62 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
printer.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
65 | scanf("%s", C);
| ~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
1 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
1 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
1 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
588 KB |
Output is correct |
| 2 |
Correct |
2 ms |
972 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1356 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
3532 KB |
Output is correct |
| 2 |
Correct |
20 ms |
7108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
8104 KB |
Output is correct |
| 2 |
Correct |
10 ms |
2252 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
67 ms |
19712 KB |
Output is correct |
| 2 |
Correct |
139 ms |
45012 KB |
Output is correct |
| 3 |
Correct |
81 ms |
23520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
15456 KB |
Output is correct |
| 2 |
Correct |
166 ms |
53372 KB |
Output is correct |
| 3 |
Correct |
92 ms |
26588 KB |
Output is correct |
| 4 |
Correct |
131 ms |
50452 KB |
Output is correct |
