#include<bits/stdc++.h>
#include <random>
using namespace std;
namespace NEO {
std::mt19937 cincai(std::chrono::steady_clock::now().time_since_epoch().count());
using i64 = long long;
#define pb push_back
#define mp make_pair
#define cs constexpr
#define L(i,j,k) for(int i=(j);i<=(k);++i)
#define R(i,j,k) for(int i=(j);i>=(k);--i)
#define all(x) x.begin(),x.end()
#define me(x,a) memset(x,a,sizeof(x))
//~ #ifndef ONLINE_JUDGE
//~ #include "debug.h"
//~ #else
//~ #define dbg(...) 43
//~ #endif
}
using namespace NEO;
struct node {
int nxt[26];
bool is_longest, finish_word;
node() {
me(nxt, 0);
is_longest = false;
finish_word = false;
}
};
cs int _N = 25000 * 21;
int tot = 0;
node trie[_N];
void build(string S) {
int M = S.size(), P = 0;
for (int i = 0; i < M; i++) {
int nw = S[i] - 'a';
if (trie[P].nxt[nw] == 0) {
trie[P].nxt[nw] = ++tot;
trie[tot] = node();
}
P = trie[P].nxt[nw];
}
trie[P].finish_word = true;
}
void paint(string S) {
int P = 0;
for (int i = 0; i < (int)S.size(); i++) {
int nw = S[i] - 'a';
P = trie[P].nxt[nw];
trie[P].is_longest = true;
}
}
string ans = "";
void dfs(int P) {
int longest = -1;
if (trie[P].finish_word) ans += 'P';
for (int i = 0; i < 26; i++) {
int next_node = trie[P].nxt[i];
if (trie[next_node].is_longest) longest = i;
else if (next_node != 0) {
ans += (i + 'a');
dfs(next_node);
}
}
if (longest != -1) {
ans += (longest + 'a');
dfs(trie[P].nxt[longest]);
}
else if (longest == -1 && trie[P].is_longest) return;
else ans += '-';
}
namespace fast {
#pragma GCC optimize(Ofast)
#pragma GCC optimization (unroll-loops)
#pragma GCC target(avx,avx2,fma)
#pragma GCC target(sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native)
#pragma GCC optimize(3)
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
}
using namespace fast;
inline string read_string() {
char ch = getchar(); string st1 = "";
while (!((ch >= 'A') && (ch <= 'Z'))) ch = getchar();
while ((ch >= 'A') && (ch <= 'Z')) st1 += ch, ch = getchar();
return st1;
}
char buf[1 << 23], * p1 = buf, * p2 = buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
template<typename T> inline void re(T& x) { x = 0; T f = 1; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { x = x * (1 << 1) + x * (1 << 3) + (ch - 48); ch = getchar(); } x *= f; }
template<typename x, typename... y>void re(x& a, y&... b) { re(a); re(b...); }
template<typename T> inline void ps(T x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9) ps(x / 10); putchar(x % 10 + '0'); }
template<typename x, typename... y>void ps(x& a, y&... b) { ps(a); putchar(' '); ps(b...); }
#define sp putchar(' ')
#define nl putchar('\n')
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int N; re(N);
vector<string> s(N + 1);
L(i, 1, N) s[i] = read_string();
string longest = "";
L(i, 1, N) {
build(s[i]);
if (longest.size() < s[i].size())
longest = s[i];
}
paint(longest);
dfs(0);
ps(ans.size()); nl;
for (auto& c : ans) putchar(c), nl;
}
Compilation message
printer.cpp:80: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
80 | #pragma GCC optimization (unroll-loops)
|
printer.cpp:79:26: warning: '#pragma GCC optimize' is not a string or number [-Wpragmas]
79 | #pragma GCC optimize(Ofast)
| ^~~~~
printer.cpp:81:24: warning: '#pragma GCC option' is not a string [-Wpragmas]
81 | #pragma GCC target(avx,avx2,fma)
| ^~~
printer.cpp:82:24: warning: '#pragma GCC option' is not a string [-Wpragmas]
82 | #pragma GCC target(sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native)
| ^~~
printer.cpp:102:43: warning: bad option '-fwhole-program' to pragma 'optimize' [-Wpragmas]
102 | #pragma GCC optimize("-fwhole-program")
| ^
printer.cpp:109:45: warning: bad option '-fstrict-overflow' to pragma 'optimize' [-Wpragmas]
109 | #pragma GCC optimize("-fstrict-overflow")
| ^
printer.cpp:111:45: warning: bad option '-fcse-skip-blocks' to pragma 'optimize' [-Wpragmas]
111 | #pragma GCC optimize("-fcse-skip-blocks")
| ^
printer.cpp:125:55: warning: bad option '-funsafe-loop-optimizations' to pragma 'optimize' [-Wpragmas]
125 | #pragma GCC optimize("-funsafe-loop-optimizations")
| ^
printer.cpp:131:27: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
131 | inline string read_string() {
| ^
printer.cpp:131:27: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
printer.cpp:131:27: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
printer.cpp:131:27: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
printer.cpp:139:41: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
139 | template<typename T> inline void re(T& x) { x = 0; T f = 1; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { x = x * (1 << 1) + x * (1 << 3) + (ch - 48); ch = getchar(); } x *= f; }
| ^
printer.cpp:139:41: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
printer.cpp:139:41: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
printer.cpp:139:41: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
printer.cpp:140:57: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
140 | template<typename x, typename... y>void re(x& a, y&... b) { re(a); re(b...); }
| ^
printer.cpp:140:57: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
printer.cpp:140:57: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
printer.cpp:140:57: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
printer.cpp:141:40: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
141 | template<typename T> inline void ps(T x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9) ps(x / 10); putchar(x % 10 + '0'); }
| ^
printer.cpp:141:40: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
printer.cpp:141:40: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
printer.cpp:141:40: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
printer.cpp:142:57: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
142 | template<typename x, typename... y>void ps(x& a, y&... b) { ps(a); putchar(' '); ps(b...); }
| ^
printer.cpp:142:57: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
printer.cpp:142:57: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
printer.cpp:142:57: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
printer.cpp:146:10: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
146 | int main() {
| ^
printer.cpp:146:10: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
printer.cpp:146:10: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
printer.cpp:146:10: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1061 ms |
57692 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1016 ms |
57692 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1047 ms |
57692 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1008 ms |
57688 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1084 ms |
57592 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1048 ms |
57692 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1029 ms |
57948 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1044 ms |
58456 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1016 ms |
60760 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1047 ms |
61016 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
