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>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#ifdef dremix
#define p(x) cerr<<#x<<" = "<<x<<endl;
#define p2(x,y) cerr<<#x<<" , "<<#y<<" = "<<x<<" , "<<y<<endl;
#define pp(x) cerr<<#x<<" = ("<<x.F<<" , "<<x.S<<")"<<endl;
#define pv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u<<", ";cerr<<"}"<<endl;
#define ppv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u.F<<"-"<<u.S<<", ";cerr<<"}"<<endl;
#else
#define p(x) {}
#define p2(x,y) {}
#define pp(x) {}
#define pv(x) {}
#define ppv(x) {}
#endif
#define fastio ios_base::sync_with_stdio(false);cin.tie(nullptr);
const int maxp = 22;
const ld EPS = 1e-18;
const ll INF = 2e18;
const int MOD = 1e9+7;
const int N = 5e5+5;
struct ano{
int nxt[26] = {};
bool word = false;
};
ano trie[N];
int curr = 2;
void add(string &s){
int i = 1;
for(auto x : s){
int nxt = trie[i].nxt[x-'a'];
if(!nxt){
trie[i].nxt[x-'a'] = curr;
nxt = curr++;
}
i = nxt;
}
trie[i].word = true;
}
int deep[N];
void dfs(int s){
for(int i=0;i<26;i++){
int x = trie[s].nxt[i];
if(!x)continue;
dfs(x);
deep[s] = max(deep[s],deep[x]);
}
deep[s] ++;
}
string ans = "";
void solve(int s){
vector<pi> go;
for(int i=0;i<26;i++){
int x = trie[s].nxt[i];
if(!x)continue;
go.push_back({deep[x],i});
}
sort(all(go));
//ppv(go)
if(trie[s].word)
ans += 'P';
for(auto x : go){
ans += (char)(x.S + 'a');
solve(trie[s].nxt[x.S]);
ans += '-';
}
//p(ans)
}
int main(){
fastio
int n;
cin>>n;
int i;
for(i=0;i<n;i++){
string s;cin>>s;
add(s);
}
dfs(1);
/*
for(i=1;i<curr;i++){
p2(deep[i],trie[i].word)
for(int j=0;j<26;j++){
if(!trie[i].nxt[j])continue;
p2((char)(j+'a'),trie[i].nxt[j])
}
}*/
solve(1);
while(ans.back() == '-')ans.pop_back();
cout<<sz(ans)<<endl;
for(auto x : ans)
cout<<x<<endl;
}
# | 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... |