Submission #1177938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177938		giabao249	Type Printer (IOI08_printer)	C++20	0 / 100	1 ms	328 KiB

printer

#include<bits/stdc++.h>
using namespace std;
#define el '\n'
#define int long long
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) {
    int maxdepth = -1;
    for(int i = 0 ; i < ALPHA_BET ; i++) {
        if(p->child[i] != nullptr) {
            if(ckmax(maxdepth, p->child[i]->depth)){
                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]);
    }
}
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();
}

Compilation message (stderr)

printer.cpp: In function 'int32_t main()':
printer.cpp:89:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     freopen("Task.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 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