Submission #993893

#	Time	Username	Problem	Language	Result	Execution time	Memory
993893		May27_th	Type Printer (IOI08_printer)	C++17	100 / 100	130 ms	105552 KiB

printer

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

#define int64_t long long
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()

const int MAXN = 2e5 + 10;
struct Trie {
    struct Node {
        Node* child[26];
        int exist, cnt, depth;

        Node () {
            for (int i = 0; i < 26; i ++) child[i] = NULL;
            exist = cnt = depth = 0;
        }
    };

    int cur;
    int have;
    Node* root;
    Trie() : have(0), cur(0) {
        root = new Node();
    };

    void Add(string S) {
        Node* p = root;
        for (auto f : S) {
            int c = f - 'a';
            if (p->child[c] == NULL) {
                cur ++;
                p->child[c] = new Node();
            }
            p = p->child[c];
            p->cnt ++;
        }
        p->exist ++;
        have ++;
    }
    bool DeleteR(Node* p, string S, int pos) {
        if (pos != (int)S.size()) {
            int c = S[pos] - 'a';
            bool isDeleted = DeleteR(p->child[c], S, pos + 1);
            if (isDeleted) p->child[c] = NULL;
        } else {
            p->exist --;
        }

        if (p != root) {
            p->cnt --;
            if (p->cnt == 0) {
                delete(p);
                return true;
            }
        }
        return false;
    }
    void Delete(string S) {
        if (!find(S)) return;
        DeleteR(root, S, 0);
    }

    bool find(string S) {
        Node* p = root;
        for (auto f : S) {
            int c = f - 'a';
            if (p->child[c] == NULL) return false;
            p = p->child[c];
        }
        return true;
    }
    void dfs(Node* p) {
        for (int c = 0; c < 26; c ++) {
            if (p->child[c] != NULL) {
                dfs(p->child[c]);
                p->depth = max(p->depth, p->child[c]->depth + 1);
            }
        }
    }
    void dfs1(Node* p) {
        int mx = -1;
        if (p->exist) {
            cout << "P" << "\n";
            have --;
        }
        for (int c = 0; c < 26; c ++) {
            if (p->child[c] != NULL && (mx == -1 || p->child[c]->depth > p->child[mx]->depth)) {
                mx = c;
            }
        }
        for (int c = 0; c < 26; c ++) {
            if (c != mx && p->child[c] != NULL) {
                cout << char(c + 'a') << "\n";
                dfs1(p->child[c]);
                if (have) cout << '-' << "\n";
            }
        }
        if (mx != -1) {
            cout << char(mx + 'a') << "\n";
            dfs1(p->child[mx]);
            if (have) cout << '-' << "\n";
        }
    }
    void Solve(void) {
        Node* p = root;
        // cout << p->depth << "\n";
        dfs(p);
        cout << cur * 2 + have - p->depth << "\n";
        // cout << p->depth << "\n";
        dfs1(p);
    }
};
void Solve(void) {
    int N; cin >> N;
    Trie printer;
    for (int i = 1; i <= N; i ++) {
        string S; cin >> S;
        printer.Add(S);
    }
    printer.Solve();
}
signed main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int Tests = 1; // cin >> Tests; 
    while (Tests --) {
        Solve();    
    }
}

Compilation message (stderr)

printer.cpp: In constructor 'Trie::Trie()':
printer.cpp:22:9: warning: 'Trie::have' will be initialized after [-Wreorder]
   22 |     int have;
      |         ^~~~
printer.cpp:21:9: warning:   'int Trie::cur' [-Wreorder]
   21 |     int cur;
      |         ^~~
printer.cpp:24:5: warning:   when initialized here [-Wreorder]
   24 |     Trie() : have(0), cur(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