Submission #1322705

#TimeUsernameProblemLanguageResultExecution timeMemory
1322705hana_sherif29Type Printer (IOI08_printer)C++20
100 / 100
84 ms51116 KiB
#include <bits/stdc++.h>
#include <iomanip>
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define ld long double
#define el '\n'
#define INF 1e18
//#define  int ll
using namespace std;
const ll mod = 1e9 + 7;
const ll inf = 1e9;
const ll MOD = 998244353;

const int MAXV = 200000;
const int MOD1 = 1000000007;
const int MOD2 = 1000000009;
const int BASE = 911382323;

int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};

struct Node {
    int next[26];
    bool isWord;
    int mxD;
    Node() {
        memset(next, -1, sizeof(next));
        isWord = false;
        mxD = 0;
    }
};

vector<Node> trie;
vector<char> ops;

int calc(int u) {
    int best = trie[u].isWord ? 0 : -1;
    for (int c = 0; c < 26; c++) {
        int v = trie[u].next[c];
        if (v != -1) {
            best = max(best, 1 + calc(v));
        }
    }
    trie[u].mxD = best;
    return best;
}

void dfs(int u) {
    if (trie[u].isWord) {
        ops.push_back('P');
    }
    vector<int> children;
    for (int c = 0; c < 26; c++) {
        if (trie[u].next[c] != -1) {
            children.push_back(c);
        }
    }
    sort(children.begin(), children.end(), [&](int a, int b) {
        return trie[trie[u].next[a]].mxD < trie[trie[u].next[b]].mxD;
    });
    for (int c : children) {
        int v = trie[u].next[c];
        ops.push_back('a' + c);
        dfs(v);
        ops.push_back('-');
    }
}
void H_H() {
    int n;
    cin >> n;
    trie.reserve(500000);
    trie.emplace_back();
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        int u = 0;
        for (char ch : s) {
            int c = ch - 'a';
            if (trie[u].next[c] == -1) {
                trie[u].next[c] = trie.size();
                trie.emplace_back();
            }
            u = trie[u].next[c];
        }
        trie[u].isWord = true;
    }
    calc(0);
    dfs(0);
    while (!ops.empty() && ops.back() == '-') {
        ops.pop_back();
    }
    cout << ops.size() << el;
    for (char c : ops) {
        cout << c << el;
    }
}
signed main()
{
    fast;
    ll tc = 1;
    //cin >> tc;
    while (tc--)
    {
        H_H();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...