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 ;
//monta trie
// percorre ela com dfs
// chegou ao fim printa
// qd sobe coloca -
const int maxn = 6e5 + 5 ;
int n, trie[maxn][28], ctt, qtd[maxn], fim[maxn], ct ;
string s ;
vector<char> resp ;
void add(string s){
int root = 0 ;
for(int i = 0 ; i < (int) s.size() ; i++){
if(trie[root][s[i]-'a'] == 0) trie[root][s[i]-'a'] = ++ct ;
root = trie[root][s[i]-'a'] ;
}
fim[root] = 1 ;
}
bool cmp(pair<char,int> a, pair<char,int> b){return qtd[trie[a.second][a.first-'a']] < qtd[trie[b.second][b.first-'a']] ; }
void dfs(int v, int p){
if(fim[v]){
resp.push_back('P') ; ctt++ ;
}
vector<pair<char,int>> order ;
for(char i = 'a' ; i <= 'z' ; i++){
if(trie[v][i-'a'] == 0 || trie[v][i-'a'] == p) continue ;
order.push_back({i, v}) ;
}
sort(order.begin(), order.end(), cmp) ;
// cout << v << ":\n" ;
for(auto j : order){
int i = j.first ;
// cout << j.first << " " << qtd[trie[v][j.first-'a']] << "\n" ;
resp.push_back(i) ;
dfs(trie[v][i-'a'], v) ;
}
if(ctt != n) resp.push_back('-') ;
}
void dfs_h(int v, int p){
qtd[v] = 1 ;
if(fim[v]) return ;
for(char i = 'a' ; i <= 'z' ; i++){
if(trie[v][i-'a'] == 0 || trie[v][i-'a'] == p) continue ;
dfs_h(trie[v][i-'a'], v) ;
qtd[v] = max(qtd[v], qtd[trie[v][i-'a']] + 1) ;
}
}
int main(){
ios_base::sync_with_stdio(false) ; cin.tie(NULL) ;
cin >> n ;
for(int i = 1 ; i <= n ; i++){
cin >> s ;
add(s) ;
}
dfs_h(0, 0) ; // achar a maior alt de cada um
// for(int i = 0 ; i < 4 ; i++) cout << qtd[i] << " " ;
// cout << "\n" ;
dfs(0, 0) ;
cout << resp.size() << "\n" ;
for(auto a : resp) cout << a << "\n" ;
}
# | 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... |