fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5. #define endl '\n'
  6. const int N = 525001;
  7. vector<int> adj[N];
  8. string ans = "";
  9. bitset<N> mp;
  10. bitset<N> mp2;
  11. bitset<26> vis2[N];
  12. short lst[N];
  13. void dfs(int node){
  14.     if(mp[node]) {
  15.         ans += 'P';
  16.     }
  17.     for(auto ch : adj[node]){
  18.         ans += lst[ch]+'a';
  19.         dfs(ch);
  20.         ans += '-';
  21.     }
  22. }
  23. bool cmp(int a,int b){
  24.     return mp2[b];
  25. }
  26. int main()
  27. {
  28.     ios_base::sync_with_stdio(0);
  29.     cin.tie(0);      cout.tie(0);
  30.     int t=1;
  31.     // cin>>t;
  32.     while(t--){
  33.         int n;
  34.         cin>>n;
  35.         string v[n];
  36.         for(auto &i:v) cin>>i;
  37.         string mx = "";
  38.         for(auto i : v){
  39.             if(i.size()>mx.size()) mx = i;
  40.         }
  41.         map<string,int> id;
  42.         int cnt = 1;
  43.         for(int i=0;i<n;i++){
  44.             string tmp = "";
  45.             for(int j=0;j<v[i].size();j++){
  46.                 tmp += v[i][j];
  47.                 if(!id.count(tmp)){
  48.                     id[tmp] = cnt++;
  49.                     lst[id[tmp]] = v[i][j]-'a';
  50.                 }
  51.             }
  52.             mp[id[tmp]] = 1;
  53.         }
  54.         string tmp = "";
  55.         for(int i=0;i<n;i++){
  56.             tmp = "";
  57.             for(auto j : v[i]){
  58.                 if(!vis2[id[tmp]][j-'a']){
  59.                     adj[id[tmp]].push_back(id[tmp+j]);
  60.                     vis2[id[tmp]][j-'a'] = 1;
  61.                 }
  62.                 tmp += j;
  63.             }
  64.         }
  65.         tmp = "";
  66.         for(int i=0;i<mx.size();i++){
  67.             mp2[id[tmp]] = 1;
  68.             tmp += mx[i];
  69.         }
  70.         for(auto &i : adj){
  71.             if(i.size())sort(i.begin(),i.end(),cmp);
  72.         }
  73.         dfs(0);
  74.         while(ans.size()&&ans.back()=='-') ans.pop_back();
  75.         cout<<ans.size()<<endl;
  76.         for(auto i : ans) cout<<i<<endl;
  77.     }
  78.     return 0;
  79. }
  80.  
Success #stdin #stdout 0.01s 17160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
P
https://ideone.com/1A8cne
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!