제출 #1218336

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1218336		sunflower	Type Printer (IOI08_printer)	C++17	100 / 100	141 ms	112708 KiB

printer

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define SZ(x) ((int) (x).size())
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define debug(x) cout << "[" << #x << " = " << (x) << "]" << endl

#define left    __left
#define right   __right
#define prev    __prev
#define next    __next
#define fi      first
#define se      second

template <class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) return x = y, true;
        else return false;
    }

template <class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) return x = y, true;
        else return false;
    }


const int ALPHABET_SIZE = 26;
struct Node {
    Node* child[ALPHABET_SIZE];
    int cnt, high, maxHigh;

    Node() {
        REP(i, ALPHABET_SIZE) child[i] = nullptr;
        cnt = 0;
        high = 0, maxHigh = 0;
    }
};

typedef Node* node;

#define MAX_NODE 500'500
Node nodes[MAX_NODE + 2];
int trieNode;
Node *root;

Node* createNode() {
    return &nodes[trieNode++];
}

void addString(const string &s) {
    Node* p = root;
    for (char c : s) {
        int x = c - 'a';
        if (p->child[x] == nullptr) p->child[x] = createNode();
        p = p->child[x];
    }
    p->cnt++;
}

void dfs(Node *u) {
    u->maxHigh = u->high;
    REP(i, ALPHABET_SIZE) {
        if (u->child[i] == nullptr) continue;

        u->child[i]->high = u->high + 1;
        dfs(u->child[i]);
        maximize(u->maxHigh, u->child[i]->maxHigh);
    }
}

vector <char> opt;

/// cuoi cung cta chi de lai only one longest word - dont erase;
void calc(Node *u, int c) {
    if (c != -1) opt.push_back((char) c + 'a');
    if (u->cnt > 0) {
        REP(i, u->cnt) opt.push_back('P');
    }

    REP(i, ALPHABET_SIZE) {
        if (u->child[i] == nullptr) continue;

        if (u->child[i]->maxHigh != u->maxHigh) {
            calc(u->child[i], i);
        }
    }

    REP(i, ALPHABET_SIZE) {
        if (u->child[i] == nullptr) continue;

        if (u->child[i]->maxHigh == u->maxHigh) {
            calc(u->child[i], i);
        }
    }

    opt.push_back('-');
}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
//    freopen("test.inp","r",stdin);
//    freopen("test.out","w",stdout);

    root = createNode();

    int n; cin >> n;
    FOR(i, 1, n) {
        string s;
        cin >> s;
        addString(s);
    }

    dfs(root);
    calc(root, -1);

    while (!opt.empty() && opt.back() == '-') opt.pop_back();

    cout << SZ(opt) << "\n";
    for (char c : opt) cout << c << "\n";

    return 0;
}

/* Discipline - Calm */

• 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