제출 #1324052

#제출 시각아이디문제언어결과실행 시간메모리
1324052kasamchiType Printer (IOI08_printer)C++20
100 / 100
114 ms121724 KiB
#include <bits/stdc++.h>
using namespace std;

struct Node {
    bool word, last;
    vector<Node*> chd;
    Node (void) : word(false), last(false), chd(vector<Node*>(26)) {}
};

void add(int i, string &S, bool last, Node *rt) {
    if (i == (int)S.size()) {
        rt -> word = true;
    } else {
        if (last) {
            rt -> last = true;
        }
        if (rt -> chd[S[i] - 'a'] == nullptr) {
            rt -> chd[S[i] - 'a'] = new Node();
        }
        add(i + 1, S, last, rt -> chd[S[i] - 'a']);
    }
}

void dfs(Node *rt, string &ans) {
    if (rt -> word) {
        ans += 'P';
    }
    int ltr = -1;
    for (int i = 0; i < 26; i++) {
        if (rt -> chd[i] != nullptr) {
            if (rt -> chd[i] -> last) {
                ltr = i;
            } else {
                ans += (char)('a' + i);
                dfs(rt -> chd[i], ans);
            }
        }
    }
    if (ltr != -1) {
        ans += (char)('a' + ltr);
        dfs(rt -> chd[ltr], ans);
    }
    ans += '-';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N;
    cin >> N;

    vector<string> S(N);
    for (int i = 0; i < N; i++) {
        cin >> S[i];
    }

    int mxl = S[0].size(), mxp = 0;
    for (int i = 1; i < N; i++) {
        if ((int)S[i].size() > mxl) {
            mxl = S[i].size();
            mxp = i;
        }
    }

    Node *root = new Node();
    for (int i = 0; i < N; i++) {
        add(0, S[i], (i == mxp), root);
    }

    string ans;
    dfs(root, ans);
    cout << ans.size() - mxl - 1 << '\n';
    for (int i = 0; i < (int)ans.size() - mxl - 1; i++) {
        cout << ans[i] << '\n';
    }
}
#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...