Submission #1221081

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221081		Ariadna	Type Printer (IOI08_printer)	C++20	100 / 100	716 ms	105036 KiB

printer

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

struct Node {
    char c;
    int i, fin, sz, len;
    Node* adj[26] = {nullptr};

    Node(char c, int i) : c(c), i(i), fin(0), sz(1), len(i+1) {};
};

void add(int i, string& s, Node* Trie) {
    if (s.size() == i) {
        Trie->fin+=1;
        return;
    }

    int c = int(s[i]-'a');
    if (not Trie->adj[c]) Trie->adj[c] = new Node(c, i+1);
    add(i+1, s, Trie->adj[c]);
}

int maxl = 0;
void dfs(Node* node) {
    for (int i = 0; i < 26; ++i) {
        if (not node->adj[i]) continue;
        dfs(node->adj[i]);
        node->sz += node->adj[i]->sz;
        node->len = max(node->len, node->adj[i]->len);
    }
    maxl = max(maxl, node->len);
}

int rest, op;
void calc(Node* node) {
    if (node->c != '-') op++;
    if (node->fin) op++;
    rest--;
    for (int i = 0; i < 26; ++i) {
        if (not node->adj[i]) continue;
        if (node->adj[i]->len == maxl) continue;
        calc(node->adj[i]);
    }
    for (int i = 0; i < 26; ++i) {
        if (not node->adj[i]) continue;
        if (node->adj[i]->len != maxl) continue;
        calc(node->adj[i]);
    } 
    if (rest) op++;
}

void print(Node* node) {
    if (node->c != '-') cout << char(node->c+int('a')) << endl;
    if (node->fin) cout << 'P' << endl;
    rest--;
    for (int i = 0; i < 26; ++i) {
        if (not node->adj[i]) continue;
        if (node->adj[i]->len == maxl) continue;
        print(node->adj[i]);
    }
    for (int i = 0; i < 26; ++i) {
        if (not node->adj[i]) continue;
        if (node->adj[i]->len != maxl) continue;
        print(node->adj[i]);
    } 
    if (rest) cout << '-' << endl;
}

int main() {
    int n;
    cin >> n;
    Node* raiz = new Node('-', 0);
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        add(0, s, raiz);
    }
    dfs(raiz);
    rest = raiz->sz;
    calc(raiz);
    rest = raiz->sz;
    cout << op << endl;
    print(raiz);

    return 0;
}

• 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