#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define ll long long
#define rep(i,a,b) for (int i = a; i < b; i++)
#define rrep(i,a,b) for (int i = a; i >= b; i--)
void N() {cout<<"NO\n";}
void Y() {cout<<"YES\n";}
void isTrue(bool ope) {if (ope) Y();else N();}
ll pw(int x,int t) {ll res = 1;while (t--) res *= x;return res;}
int lg(int x,int b) {int res = 0;while (x >= b) {x/=b;res++;}return res;}
int MD = 1e9+7;
ll MX_VL = 1e18;
ll MX_ll = 2e9;
int BITS = 31;
struct Node {
char c;
vector<int> child;
bool prnt;
Node(char x,bool p) {
c = x;
rep(i,0,27) child.push_back(-1);
prnt = p;
}
};
void Insert(vector<Node>& trie,string s) {
int n = s.length();
int curr = 0;
rep(i,0,n) {
if (trie[curr].child[s[i]-'a'+1] == -1) {
trie[curr].child[s[i]-'a'+1] = trie.size();
trie.push_back(Node(s[i],false));
}
trie[trie[curr].child[s[i]-'a'+1]].prnt= i == (n-1);
curr = trie[curr].child[s[i]-'a'+1];
}
}
int countSub(vector<Node>& trie,int ind,vector<int>& cnt) {
int mx = 1;
rep(i,1,27) {
if (trie[ind].child[i] != -1) {
mx = max(mx,1+countSub(trie,trie[ind].child[i],cnt));
}
}
cnt[ind] = mx;
return mx;
}
int lft;
vector<char> ans;
void printV(vector<Node>& trie,int ind,vector<int>& cnt) {
if (ind!=0) ans.push_back(trie[ind].c);
if (trie[ind].prnt) {
ans.push_back('P');
lft--;
}
vector<pair<int,int>> v;
rep(i,1,27) {
if (trie[ind].child[i]==-1) continue;
v.push_back(make_pair(cnt[trie[ind].child[i]],i));
}
sort(v.begin(),v.end());
for (auto pr:v) {
printV(trie,trie[ind].child[pr.second],cnt);
}
if (lft > 0) ans.push_back('-');
}
void solve() {
int n;
cin>>n;
lft = n;
vector<Node> trie;
char pss = 'd';
trie.push_back(Node(pss,false));
int mx = 0;
rep(i,0,n) {
string s;
cin>>s;
int l = s.length();
mx = max(mx,l);
Insert(trie,s);
}
vector<int> cnt(trie.size(),0);
countSub(trie,0,cnt);
printV(trie,0,cnt);
cout << ans.size() << endl;
for (auto c:ans) cout << c << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
# | 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... |