Submission #1177945

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177945		giabao249	Type Printer (IOI08_printer)	C++20	20 / 100	29 ms	37956 KiB

printer

#include<bits/stdc++.h>
using namespace std;
#define el '\n'
const int N = 2e5 + 5;
const int ALPHA_BET = 26;
const int inf = 2e9;
template<class T> bool ckmax(T& a, const T&b) {
    return a < b ? a = b, 1 : 0;
}
int n;
struct Node {
    Node*child[ALPHA_BET];
    int exits, best, depth , bestChild;
    Node() {
        for(int i = 0 ; i < ALPHA_BET ; i++) {
            child[i] = nullptr;
        }
        exits = 0, best = 0, depth = 0 , bestChild = -1;
    }
};

int cur = 0;
Node *root;
void addString(string s) {
    Node *p = root;
    for(char f : s) {
        int c = f - 'a';
        if(p->child[c] == nullptr) {
            p->child[c] = new Node();
            p->child[c]->depth = p->depth + 1;
        }
        p = p->child[c];
    }
    p->exits++;
}

void dfs(Node *p) {
    p->best = p->depth;
    for(int i = 0 ; i < ALPHA_BET ; i++) {
        if(p->child[i] != nullptr) {
            dfs(p->child[i]);
            if(ckmax(p->best, p->child[i]->best)){
                p->bestChild = i;
            }
        }
    }
}
vector<char> ret;
void solve(Node *p) {
    if(p->exits > 0){
        ret.push_back('P');
        return;
    }
    for(int i = 0 ; i < ALPHA_BET ; i++){
        if(p->child[i]){
            if(i != p->bestChild){
                ret.push_back(char(i + 'a'));
                solve(p->child[i]);
                ret.push_back('-');
            }
        }
    }
    if(p->bestChild != -1){
        ret.push_back(char(p->bestChild + 'a'));
        solve(p->child[p->bestChild]);
        ret.push_back('-');
    }
}
void GOTO_OLP2025() {
    root = new Node();
    cin >> n;
    for(int i = 0 ; i < n ; i++) {
        string s ;
        cin >> s;
        addString(s);
    }
    dfs(root);
    solve(root);
    for(int i = ret.size() - 1 ; i >= 0 ; i--){
        if(ret[i] == '-') ret.pop_back();
        else break;
    }
    cout << ret.size() << el;
    for(char c : ret) cout << c << el;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("Task.in", "r", stdin);
    GOTO_OLP2025();
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10