Submission #1176518

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176518		justok	Type Printer (IOI08_printer)	C++20	60 / 100	1097 ms	58480 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;
    vector<char> go(string s) {
        ans.clear();
        dfs(0, 0, s, 1);
        return ans;
    }
    void dfs(int idx, int i, string &s, bool cur) {
        if (tree[idx].en) {
            ans.push_back('P');
        }
        for (int j = 0; j < 26; ++j) {
            int nxt = tree[idx].vis[j];
            if (nxt) {
                if (!cur || i >= s.size() || j != s[i] - 'a') {
                    ans.push_back(j + 'a');
                    dfs(nxt, i + 1, s, 0);
                    ans.push_back('-');
                }
            }
        }
        if (i < s.size() && cur) {
            ans.push_back(s[i]);
            dfs(tree[idx].vis[s[i] - 'a'], i + 1, s, 1);
        }
    }
};

void JustOK() {
    int n; cin >> n;
    Trie t;
    string s[n];
    for (int i = 0; i < n; ++i) {
        cin >> s[i];
        t.add(s[i]);
    }
    vector<char> ans;
    for (int i = 0; i < n; ++i) {
        auto cur = t.go(s[i]);
        if (ans.empty() || cur.size() < ans.size()) {
            ans = cur;
        }
    }
    cout << ans.size() << '\n';
    for (auto &i : ans)
        cout << i << '\n';
}
signed main() {
    FADY;
    int tc = 1;
    // cin >> tc;
    while (tc--)
        JustOK();
}

• 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: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10