#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define FAST ios_base::sync_with_stdio(false), cin.tie(NULL) , cout.tie(NULL)
#define endl "\n"
#define vi vector<int>
#define vvi vector<vector<int> >
#define vpii vector<pair<int , int> >
#define vc vector<char>
#define vvc vector<vector<char> >
#define mii map<int , int>
#define pii pair<int , int>
#define vb vector<bool>
#define vvb vector<vector<bool> >
#define pb push_back
#define ppb pop_back
#define ff first
#define ss second
#define fr(i,n) for(int i=0; i<(n); i++)
#define dbg(var) cout<<#var<<" : "<<var<<"\n"
#define all(v) v.begin(),v.end()
#define srt(v) sort(v.begin(),v.end()) // sort
#define mxe(v) *max_element(v.begin(),v.end()) // find max element in vector
#define mne(v) *min_element(v.begin(),v.end()) // find min element in vector
#define unq(v) v.resize(distance(v.begin(), unique(v.begin(), v.end())));
// make sure to sort before applying unique // else only consecutive duplicates would be removed
#define bin(x,y) bitset<y>(x)
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define set_bits(x) __builtin_popcountll(x) // number of set bits
#define first_set(x) __builtin_ctzll(x) // ...001000 -> 3
#define last_set(x) __builtin_ctzll(x) // 00010000 00000000 00000000 00000000 -> 3 (for 32 bit int), not very useful tho
using namespace std;
const int MOD=1e9+7; // Hardcoded, directly change from here for functions!
// using namespace __gnu_pbds;
using __gnu_pbds::tree;
using __gnu_pbds::rb_tree_tag;
using __gnu_pbds::tree_order_statistics_node_update;
using __gnu_pbds::null_type;
// _GLIBCXX_DEBUG must not be defined otherwise some internal check will fail
#undef _GLIBCXX_DEBUG
template <typename K, typename V, typename Comp = less<K>>
using indexed_map = tree<K, V, Comp, rb_tree_tag, tree_order_statistics_node_update>;
template <typename K, typename Comp = less<K>>
using indexed_set = indexed_map<K, null_type, Comp>;
// ¡¡IMPORTANT!! (for using less_equals<K>)
// using less_equals<K> makes lower_bound works as upper_bound and vice-versa
// for erase use: any.erase(any.find_by_order(any.order_of_key(val)));
// don't use .find() because it will always return .end()
template <typename K, typename V, typename Comp = less_equal<K>>
using indexed_multimap = indexed_map<K, V, Comp>;
template <typename K, typename Comp = less_equal<K>>
using indexed_multiset = indexed_map<K, null_type, Comp>;
// find_by_order(k): returns an iterator to the (k+1)-th largest element (0-based)
// order_of_key(num): #elements in the set strictly smaller "num"
void modadd(int &a , int b) {a=((a%MOD)+(b%MOD))%MOD;}
void modsub(int &a , int b) {a=((a%MOD)-(b%MOD)+MOD)%MOD;}
void modmul(int &a , int b) {a=((a%MOD)*(b%MOD))%MOD;}
// ================================== take ip/op like vector,pairs directly!==================================
template<typename typC,typename typD> istream &operator>>(istream &cin,pair<typC,typD> &a) { return cin>>a.first>>a.second; }
template<typename typC> istream &operator>>(istream &cin,vector<typC> &a) { for (auto &x:a) cin>>x; return cin; }
template<typename typC,typename typD> ostream &operator<<(ostream &cout,const pair<typC,typD> &a) { return cout<<a.first<<' '<<a.second; }
template<typename typC,typename typD> ostream &operator<<(ostream &cout,const vector<pair<typC,typD>> &a) { for (auto &x:a) cout<<x<<'\n'; return cout; }
template<typename typC> ostream &operator<<(ostream &cout,const vector<typC> &a) { int n=a.size(); if (!n) return cout; cout<<a[0]; for (int i=1; i<n; i++) cout<<' '<<a[i]; return cout; }
template<typename typC> ostream &operator<<(ostream &cout,const set<typC> &a) { for (auto it:a) cout<<it << " "; return cout; }
template<typename typC> ostream &operator<<(ostream &cout,const multiset<typC> &a) { for (auto it:a) cout<<it << " "; return cout; }
template<typename typC,typename typD> ostream &operator<<(ostream &cout,const map<typC , typD> &m) { for (auto it:m) cout<<it.ff << " : " << it.ss << endl; return cout; }
// ===================================END Of the input module ==========================================
const int W = 5e5 + 5;
int trie[26][W];
int node_cnt;
int en[W];
void add(string s){
int n = s.size();
int x = 0; // root
for(int i=0;i<s.size();i++){
int cur = s[i]-'a';
if(trie[cur][x] == 0){
trie[cur][x] = ++node_cnt;
}
x = trie[cur][x];
}
en[x] += 1;
}
int height[W];
void dfs1(int u){
for(int i=0;i<26;i++){
if(trie[i][u] != 0){
int v = trie[i][u];
dfs1(v);
height[u] = max(height[u] , 1+height[v]);
}
}
}
string ans;
void dfs(int u , string &s){
if(en[u] != 0){
// end of a word
ans += 'P';
}
vvi choices;
for(int i=0;i<26;i++){
if(trie[i][u] != 0){
int v = trie[i][u];
int kk = height[v];
choices.pb({kk , v , i});
}
}
srt(choices);
fr(i,choices.size()){
char add = 'a' + choices[i][2];
ans += add;
s += add;
dfs(choices[i][1] , s);
}
ans += '-';
s.pop_back();
}
void solve(){
int n;
cin >> n;
fr(i,n){
string s;
cin >> s;
add(s);
}
// do a dfs on the trie created
// FIRST, get the height for priority
dfs1(0);
string temp = "";
dfs(0 , temp);
while(ans.back() == '-')ans.pop_back();
cout << ans.size() << endl;
fr(i,ans.size())cout << ans[i] << endl;
}
int32_t main()
{
FAST;
int T=1;
// cin >> T;
for (int cas=1;cas<=T;cas++)
{
// cout << "Case #" << case << ": " << endl;
solve();
// if(case == _){
// int n;
// cin >> n;
// vi a(n);
// cin >> a;
// cout << n << "_";
// fr(i,n)cout << a[i] << "_";
// }
// else solve();
}
return 0;
}
Compilation message
printer.cpp: In function 'void add(std::string)':
printer.cpp:90:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(int i=0;i<s.size();i++){
| ~^~~~~~~~~
printer.cpp:88:6: warning: unused variable 'n' [-Wunused-variable]
88 | int n = s.size();
| ^
printer.cpp: In function 'void dfs(long long int, std::string&)':
printer.cpp:20:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | #define fr(i,n) for(int i=0; i<(n); i++)
| ^
printer.cpp:131:2: note: in expansion of macro 'fr'
131 | fr(i,choices.size()){
| ^~
printer.cpp: In function 'void solve()':
printer.cpp:20:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | #define fr(i,n) for(int i=0; i<(n); i++)
| ^
printer.cpp:162:2: note: in expansion of macro 'fr'
162 | fr(i,ans.size())cout << ans[i] << endl;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2648 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2648 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3412 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4188 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4440 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8028 KB |
Output is correct |
| 2 |
Correct |
20 ms |
16476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
18668 KB |
Output is correct |
| 2 |
Correct |
8 ms |
5468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
77 ms |
39460 KB |
Output is correct |
| 2 |
Correct |
164 ms |
85000 KB |
Output is correct |
| 3 |
Correct |
87 ms |
46092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
31980 KB |
Output is correct |
| 2 |
Correct |
201 ms |
100364 KB |
Output is correct |
| 3 |
Correct |
99 ms |
51696 KB |
Output is correct |
| 4 |
Correct |
134 ms |
94988 KB |
Output is correct |
