This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define file(name) freopen(name".inp" , " r " , stdin);freopen(name".out" , " w " , stdout)
#define faster ios_base :: sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;
#define pii pair < int , int >
#define pdd pair < double , double >
#define fi first
#define se second
#define mii map< int , int>
#define mdd map< double , double >
#define qi queue < int >
#define dqi deque< int >
#define pf(x) push_front(x)
#define popf pop_front()
#define reset(a,val) memset(a ,val , sizeof(a) )
#define count_bit(i) __builtin_popcountll(i)
#define mask(i) ((1LL << (i)))
#define status(x, i) (((x) >> (i)) & 1)
#define set_on(x, i) ((x) | mask(i))
#define set_off(x, i) ((x) & ~mask(i))
#define endl '\n'
#define int long long
const int maxn = 1e6 + 6;
const int mod= 1e9 + 7;
const int INF= 1e9;
const int LOG = 20 ;
template <class T> inline T sqr(T x) { return x * x; };
template <class T> inline int Power(T x, int y)
{ if (!y) return 1; if (y & 1) return sqr(Power(x, y / 2)) % mod * x % mod; return sqr(Power(x, y / 2)) % mod; }
template<class T> bool minimize(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool maximize(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
inline int gcd(int x, int y)
{ return y ? gcd(y , x % y) : x;}
inline int lcm(int x, int y) { return x * y / gcd(x, y); }
using namespace std;
vector<char> ans;
int idx = 0;
int n;
struct Trie{
struct Node{
Node* child[26];
int exits ;
int sz;
Node()
{
for (int i=0 ; i<26 ; ++i) child[i] = NULL;
exits = 0;
sz = 1;
}
};
Node* root;
Trie()
{
root = new Node;
};
void add(string s)
{
Node* p = root;
for (int i=0 ; i < (int)s.size() ; ++i)
{
int c = s[i] - 'a';
if (p->child[c] == NULL) { p->child[c] = new Node ; }
p=p->child[c];
}
p->exits++;
}
void dfs(Node* p)
{
p->sz = 1;
for (int i=0 ; i<26 ; ++i)
if (p->child[i] != NULL)
{
dfs(p->child[i]);
p->sz = max(p->sz , p->child[i]->sz + 1);
}
}
void get_ans(Node* p)
{
if (p->exits != 0)
{
ans.push_back('P');
idx++;
}
vector<pair<int , pair<Node* , int>>> path;
for (int i=0 ; i<26 ; ++i)
if (p->child[i] != NULL)
{
path.push_back({p->child[i]->sz , {p->child[i] , i}});
}
sort(path.begin() , path.end());
for (auto it : path)
{
ans.push_back(it.se.se + 'a');
get_ans(it.se.fi);
if (idx < n) ans.push_back(45);
}
}
void prepare()
{
Node*p = root;
dfs(p);
get_ans(p);
}
};
Trie tr;
string a[maxn];
void solve()
{
cin >> n ;
for (int i=1 ; i<=n; ++i)
{
cin >> a[i];
tr.add(a[i]);
}
tr.prepare();
cout << ans.size() << endl;
// reverse(ans.begin() , ans.end());
for (auto x : ans) cout << x << endl;
}
int32_t main()
{
faster;
#ifdef ONLINE_JUDGE
file("txt");
#else
// online submission
#endif
// int t ; cin >> t ; while (t--)
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |