Submission #1320289

#TimeUsernameProblemLanguageResultExecution timeMemory
1320289khanhphucscratchType Printer (IOI08_printer)C++20
100 / 100
67 ms49808 KiB
#include<bits/stdc++.h>
using namespace std;
int trie[500005][26], h[500005], sz = 0;
bool leaf[500005];
vector<char> ans;
void add(string s)
{
    int u = 0;
    for(int i = 0; i < s.size(); i++){
        if(trie[u][s[i] - 'a'] == 0) trie[u][s[i] - 'a'] = ++sz;
        u = trie[u][s[i] - 'a'];
        h[u] = max(h[u], (int)s.size()-i-1);
    }
    leaf[u] = 1;
}
void dfs(int u, bool ret)
{
    if(leaf[u] == 1) ans.push_back('P');
    int bc = -1;
    for(int i = 0; i < 26; i++) if(trie[u][i] > 0 && (bc == -1 || h[trie[u][i]] > h[trie[u][bc]])) bc = i;
    if(bc == -1) return;
    for(int i = 0; i < 26; i++) if(trie[u][i] > 0 && i != bc){
        ans.push_back((char)(i+'a'));
        dfs(trie[u][i], 1);
        ans.push_back('-');
    }
    ans.push_back((char)(bc+'a'));
    dfs(trie[u][bc], ret);
    if(ret == 1) ans.push_back('-');
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n; cin>>n; h[0] = -1;
    for(int i = 1; i <= n; i++){
        string s; cin>>s;
        add(s);
    }
    dfs(0, 0);
    cout<<ans.size()<<'\n';
    for(char i : ans) cout<<i<<'\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...