Submission #1297037

#TimeUsernameProblemLanguageResultExecution timeMemory
1297037harryleeeType Printer (IOI08_printer)C++20
100 / 100
94 ms58012 KiB
#include<bits/stdc++.h>
using namespace std;
const int maxn = 25000;
int n;
vector<char> res;

struct TRIE{
    struct NODE{
        int nxt[26], cnt, len;
        inline NODE(){
            fill(nxt, nxt + 26, -1);
            cnt = len = 0;
        }
    }; vector<NODE> node;
    inline TRIE(){
        node.push_back(NODE());
    }
    inline void insert(const string& s){
        int pos = 0;
        for (int i = 0; i < s.size(); ++i){
            int c = s[i] - 'a';
            if (node[pos].nxt[c] == -1){
                node[pos].nxt[c] = node.size();
                node.push_back(NODE());
            }
            pos = node[pos].nxt[c];
            node[pos].len = max(node[pos].len, (int)s.size());
        }
        node[pos].cnt++;
        return;
    }
    inline void DFS(int pos){
        if (node[pos].cnt > 0) res.push_back('P');
        vector<pair<int, int>> v;
        for (int i = 0; i < 26; ++i) if (node[pos].nxt[i] != -1){
            v.push_back({node[node[pos].nxt[i]].len, i});
        }
        sort(v.begin(), v.end());
        for (pair<int, int> x : v){
            res.push_back((char)('a' + x.second));
            DFS(node[pos].nxt[x.second]);
        }
        res.push_back('-');
        return;
    }
} trie;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i){
        string s; cin >> s;
        trie.insert(s);
    }

    trie.DFS(0);
    while(res.back() == '-') res.pop_back();
    cout << res.size() << '\n';
    for (char x : res) cout << x << '\n';
    
    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...