Submission #1365139

#TimeUsernameProblemLanguageResultExecution timeMemory
1365139shrimbType Printer (IOI08_printer)C++20
100 / 100
116 ms105892 KiB
#include<bits/stdc++.h>
using namespace std;

#define int long long

struct node {
    node *adj[26];
    int dep, max_dep;
    int cnt_end;

    node () {
        for (int i = 0 ; i < 26 ; i++) adj[i] = 0;
        dep = 0;
        cnt_end = 0;
        max_dep = 0;
    }
};

node *root = new node;

void Insert (string s) {
    node *cur = root;
    for (char c : s) {
        // cur to cur -> adj[c]
        if (!cur -> adj[c - 'a']) {
            cur -> adj[c - 'a'] = new node;
        }

        cur = cur -> adj[c - 'a'];
    }
    cur -> cnt_end++;
}

void dfs1 (node *cur) {
    cur -> max_dep = cur -> dep;
    for (int i = 0 ; i < 26 ; i++) {
        if (cur -> adj[i]) {
            cur -> adj[i] -> dep = cur -> dep + 1;
            dfs1(cur -> adj[i]);
            cur -> max_dep = max(cur -> max_dep, cur -> adj[i] -> max_dep);
        }
    }
}

string ans;

void dfs2 (node *cur) {
    // cout << ans << ' ' << cur -> dep << endl;
    while (cur -> cnt_end--) {
        ans += 'P';
    }

    int m = -1;
    for (int i = 0 ; i < 26 ; i++) {
        if (cur -> adj[i]) {
            if (m == -1 || cur -> adj[i] -> max_dep > cur -> adj[m] -> max_dep) {
                m = i;
            }
        }
    }

    for (int i = 0 ; i < 26 ; i++) {
        if (i != m && cur -> adj[i]) {
            ans += 'a' + i;
            dfs2(cur -> adj[i]);
            ans += '-';
        }
    }

    if (m != -1) {
        ans += 'a' + m;
        dfs2(cur -> adj[m]);
        ans += '-';
    }
}
 

signed main () {

    int n;
    cin >> n;
    for (int i = 0 ; i < n ; i++) {
        string s; cin >> s;
        Insert(s);
    }

    dfs1(root);
    dfs2(root);

    while (ans.back() == '-') ans.pop_back();
    cout << ans.size() << '\n';
    for (char c : ans) cout << c << '\n';

}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...