Submission #1327617

#TimeUsernameProblemLanguageResultExecution timeMemory
1327617_maiiType Printer (IOI08_printer)C++20
100 / 100
108 ms57948 KiB
#include <bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define ll long long
#define all(a) a.begin(), a.end()
#define endl '\n'
const int ALPHA = 26;
const char ZERO = 'a';
vector<char> ans;
struct Trie {
    struct Node {
        int child[ALPHA]{};
        int max_depth = 0;
        bool is_end = false;
    };
    vector<Node> trie;
    Trie() {
        trie.emplace_back();
    }
    void insert(const string &s) {
        int idx = 0;
        for(auto c : s)
        {
            int curr = c - ZERO;
            if(!trie[idx].child[curr])
            {
                trie[idx].child[curr] = trie.size();
                trie.emplace_back();
            }
            idx = trie[idx].child[curr];
        }
        trie[idx].is_end = 1;
    }
    int getDepth(int idx) {
        int mx = 0;
        for(int i = 0; i < ALPHA; i++)
        {
            if(trie[idx].child[i])
                mx = max(mx, 1 + getDepth(trie[idx].child[i]));
        }
        return trie[idx].max_depth = mx;
    }
    void dfs(int idx) {
        if(trie[idx].is_end)
        {
            ans.push_back('P');
        }
        vector<tuple<int, int, int>> ch;
        for(int i = 0; i < ALPHA; i++)
        {
            if(trie[idx].child[i])
                ch.push_back({trie[trie[idx].child[i]].max_depth, i, trie[idx].child[i]});
            
        }
        sort(all(ch));
        for(auto &[len, c, i] : ch)
        {
            ans.push_back(c + ZERO);
            dfs(i);
            ans.push_back('-');
        }
    }
};
void solve() {
    int n;
    cin >> n;
    Trie tr = Trie();
    for (int i = 0; i < n; i++) 
    {
        string s;
        cin >> s;
        tr.insert(s);
    }
    tr.getDepth(0);
    tr.dfs(0);
    while (!ans.empty() && ans.back() == '-') {
        ans.pop_back();
    }
    cout << ans.size() << endl;
    for (char c : ans) {
        cout << c << endl;
    }
}
int main()
{
    FIO;
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}
#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...