Submission #1365251

#TimeUsernameProblemLanguageResultExecution timeMemory
1365251abmr59Type Printer (IOI08_printer)C++20
100 / 100
111 ms106084 KiB
#include "bits/stdc++.h"
#define mod 1000000007
#define inf 4000000000000000000
using namespace std;
#define int long long
 
struct node{
    node* adj[26];
    int dep, maxd, num;
    node(){
        for(int i=0; i<26; i++) adj[i]=0;
        dep=0; maxd=0;
        num=0;
    }
};
string ans;
node* root = new node;
void Insert(string s){
    node* cur = root;
    for(char c : s) {
        if(!cur -> adj[c-'a']) cur -> adj[c-'a'] = new node;
        cur = cur->adj[c-'a'];
    }
    cur -> num++;
}

void dfs1(node* cur){
    cur -> maxd = cur -> dep;
    for(int i=0; i<26; i++){
        if(cur -> adj[i]){
            cur -> adj[i] -> dep = cur -> dep +1;
            dfs1(cur -> adj[i]);
            cur -> maxd=max(cur -> adj[i] -> maxd, cur -> maxd);
        }
    }
}
void dfs2(node* cur){
    while(cur -> num--) ans+="P";
    int m=-1;
    for(int i=0; i<26; i++){
        if(cur -> adj[i]){
            if(m==-1 or cur -> adj[i] -> maxd > cur -> adj[m] -> maxd) m=i;
        }
    }
    for(int i=0; i<26; i++) if(cur -> adj[i]){
        if(cur -> adj[i] and i!=m){
            ans+=i+'a';
            dfs2(cur -> adj[i]);
            ans+='-';
        }
    }
    if(m!=-1){
        ans+=m+'a';
        dfs2(cur -> adj[m]);
        ans+='-';
    }
}

signed main(){
    int n; cin>>n;
    for(int i=0; i<n; i++){
        string s; cin>>s;
        Insert(s);
    }
    dfs1(root); dfs2(root);
    while(ans.back()=='-') ans.pop_back();
    cout<<ans.size()<<'\n';
    for(auto c : ans) cout<<c<<'\n';
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...