Submission #1176535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176535		justok	Type Printer (IOI08_printer)	C++20	100 / 100	203 ms	124000 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 Node {
    int vis[26]{};
    int frq = 0, en = 0;
};
vector<Node> tree;
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<vector<int>> dp;
int rec(int idx, bool cur) {
    int &ret = dp[idx][cur];
    if (~ret) return ret;
    ret = (tree[idx].en + 1 + !cur);
    int mx_dif = 0;
    for (int j = 0; j < 26; ++j) {
        int nxt = tree[idx].vis[j];
        if (nxt) {
            ret += rec(nxt, 0);
            if (cur) {
                mx_dif = max(mx_dif, rec(nxt,0) - rec(nxt,1));
            }
        }
    }
    ret -= mx_dif;
    return ret;
}
vector<char> ans;
void build(int idx, bool cur) {
    int mx_dif = 0, nxt_ch = -1;
    if (cur) {
        for (int j = 0; j < 26; ++j) {
            int nxt = tree[idx].vis[j];
            if (nxt) {
                if (rec(nxt,0) - rec(nxt,1) > mx_dif) {
                    mx_dif = rec(nxt, 0) - rec(nxt, 1);
                    nxt_ch = j;
                }
            }
        }
    }
    if (tree[idx].en) {
        ans.push_back('P');
    }
    for (int j = 0; j < 26; ++j) {
        int nxt = tree[idx].vis[j];
        if (nxt && j != nxt_ch) {
            ans.push_back(j + 'a');
            build(nxt, 0);
            ans.push_back('-');
        }
    }
    if (nxt_ch != -1) {
        ans.push_back(nxt_ch + 'a');
        build(tree[idx].vis[nxt_ch], 1);
    }
}
void JustOK() {
    tree.emplace_back();
    int n; cin >> n;
    for (int i = 0; i < n; ++i) {
        string s; cin >> s;
        add(s);
    }
    dp.resize(tree.size() + 5, vector<int>(2, -1));
    rec(0, 1);
    build(0, 1);
    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: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10