Submission #1176505

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176505		justok	Type Printer (IOI08_printer)	C++20	20 / 100	56 ms	57968 KiB

printer

#include <bits/stdc++.h> //  +
using namespace std;     // +++
#define inf 1e18         //  +
#define FADY ios_base::sync_with_stdio(0), cin.tie(0); files();
#define all(a) a.begin(), a.end()
#define int long long
string YN[2] = {"No", "Yes"};
void files()
{
// #ifndef ONLINE_JUDGE
//     freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
// #endif
}

struct Trie {
    struct Node {
        int vis[26]{};
        int frq = 0, en = 0;
    };
    vector<Node> tree;
    Trie() { tree.emplace_back(); }
    void add(string s) {
        int idx = 0;
        for (auto &i : s) {
            int ch = i - 'a';
            if (tree[idx].vis[ch] == 0) {
                tree[idx].vis[ch] = tree.size();
                tree.emplace_back();
            }   
            idx = tree[idx].vis[ch];
            tree[idx].frq++;
        }
        tree[idx].en++;
    }
    vector<char> ans;
    void dfs(int idx, bool big) {
        vector<pair<int, int>> v;
        for (int j = 0; j < 26; ++j) {
            int nxt = tree[idx].vis[j];
            if (nxt) {
                v.push_back({tree[nxt].frq, j});
            }
        } 
        if (tree[idx].en) {
            ans.push_back('P');
        }
        sort(all(v));
        for (int i = 0; i < v.size(); ++i) {
            auto [f, ch] = v[i];
            ans.push_back(ch + 'a');
            bool nwBig = (big && (i == v.size() - 1));
            dfs(tree[idx].vis[ch], nwBig);
            if (!nwBig) {
                ans.push_back('-');
            }
        }
    }
};

void JustOK() {
    int n; cin >> n;
    Trie t;
    for (int i = 0; i < n; ++i) {
        string s; cin >> s;
        t.add(s);
    }
    t.dfs(0, 1);
    cout << t.ans.size() << '\n';
    for (auto &i : t.ans) {
        cout << i << '\n';
    }
}
signed main() {
    FADY;
    int tc = 1;
    // cin >> tc;
    while (tc--)
        JustOK();
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10