Submission #1178293

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178293		giabao249	Type Printer (IOI08_printer)	C++20	100 / 100	496 ms	126600 KiB

printer

#include<bits/stdc++.h>
using namespace std;
#define el '\n'
const int N = 25005;
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;
    Node() {
        for(int i = 0 ; i < ALPHA_BET ; i++) {
            child[i] = nullptr;
        }
        exits = 0;
    }
};
map<Node* , int> depth;

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 = p->child[c];
    }
    p->exits++;
}

void dfs(Node *p) {
    depth[p] = 1;
    for(int i = 0 ; i < ALPHA_BET ; i++){
        if(p->child[i]){
            dfs(p->child[i]);
            ckmax(depth[p] , depth[p->child[i]] + 1);
//            cout << depth[p] << ' ' << char(i + 'a') << el;
        }
    }
}
string ret;
void solve(Node *p) {
    if(p->exits > 0){
        ret += 'P';
    }
    for(int i = 0 ; i < ALPHA_BET ; i++){
        if(p->child[i] && depth[p] > depth[p->child[i]] + 1){
            ret += (char)(i + 'a');
            solve(p->child[i]);
//            cout << 1 << ' ' << ret << el;
        }
    }
    for(int i = 0 ; i < ALPHA_BET ; i++){
        if(p->child[i] && depth[p] == depth[p->child[i]] + 1){
            ret += (char)(i + 'a');
            solve(p->child[i]);
//            cout << 2 << ' ' << char(i + 'a') << el;
        }
    }
    ret += '-';
}
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(0) , cout.tie(0);
//    freopen("Task.in", "r", stdin);
    GOTO_OLP2025();
}

• 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