Submission #390512

#	Time	Username	Problem	Language	Result	Execution time	Memory
390512		ngpin04	Type Printer (IOI08_printer)	C++14	100 / 100	302 ms	72180 KiB

printer

#include <bits/stdc++.h>

using namespace std;

struct trie {

    int node;
    vector <vector <int>> ptr;
    vector <int> dep;
    vector <bool> word;

    trie(int n)
    {
        ptr.assign(n + 5, vector <int> (26, 0));
        dep.assign(n + 5, 0);
        word.assign(n + 5, 0);
    }

    void add(const string &s)
    {
        int cur = 0;
        int cnt = s.size();
        for (char c : s) {
            int &p = ptr[cur][c - 'a'];
            if (!p)
                p = ++node;
            cur = p;
            dep[cur] = max(dep[cur], cnt--);
        }
        word[cur] = true;
    }

    void dfs(int u, string &ans)
    {
        vector <int> id(26); iota(id.begin(), id.end(), 0);
        sort(id.begin(), id.end(), [&](int i, int j) {
            return dep[ptr[u][i]] < dep[ptr[u][j]];
        });
        if (word[u])
            ans += 'P';
        for (int i : id) {
            int v = ptr[u][i];
            if (v == 0)
                continue;
            ans += 'a' + i;
            dfs(v, ans);
            ans += '-';
        }
    }
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("file.inp","r",stdin);
    trie tree(500000);
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        string s; cin >> s;
        tree.add(s);
    }
    string ans;
    tree.dfs(0, ans);
    while (ans.back() == '-')
        ans.pop_back();
    cout << ans.size() << "\n";
    for (char c : ans)
        cout << c << "\n";
    return 0;
}

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