Submission #824132

#	Time	Username	Problem	Language	Result	Execution time	Memory
824132		hafo	Type Printer (IOI08_printer)	C++14	100 / 100	145 ms	106472 KiB

printer

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 2e5 + 7;
const ll oo = 1e18 + 69;

int n;
vector<char> res;
string st;

struct node {
    node* child[26];
    int cnt, deep, mx, pos;

    node () {
        for(int i = 0; i < 26; i++) child[i] = NULL;
        cnt = deep = mx = 0;
    }
};

node* root = new node();

struct trie {
    void add(string &st) {
        auto p = root;
        for(int i = 0; i < Size(st); i++) {
            int nxt = st[i] - 'a';
            if(p -> child[nxt] == NULL) p -> child[nxt] = new node();
            p = p -> child[nxt];
        }
        p -> cnt++;
    }

    void dfs2(node* u) {
        u -> mx = u -> deep;
        for(int i = 0; i < 26; i++) {
            if(u -> child[i] == NULL) continue;
            auto v = u -> child[i];
            v -> deep = u -> deep + 1;
            dfs2(v);
            if(maxi(u -> mx, v -> mx)) u -> pos = i;
        }
    }

    void dfs(node* u, bool ok) {
        if(u -> cnt == 1) res.pb('P');
        for(int i = 0; i < 26; i++) {
            if(u -> child[i] == NULL || (ok && u -> pos == i)) continue;
            res.pb(char(i + 'a'));
            dfs(u -> child[i], 0);
            res.pb('-');
        }

        if(ok) {
            for(int i = 0; i < 26; i++) {
                if(u -> child[i] == NULL) continue;
                if(i == u -> pos) {
                    res.pb(char(i + 'a'));
                    dfs(u -> child[i], 1);
                }
            }
        }
    }

} trie;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    cin>>n;
    for(int i = 0; i < n; i++) {
        cin>>st;
        trie.add(st);
    }

    trie.dfs2(root);
    trie.dfs(root, 1);
    cout<<Size(res)<<"\n";
    for(auto i:res) cout<<i<<"\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