Submission #993892

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
993892	2024-06-06T18:33:41 Z	May27_th	Type Printer (IOI08_printer)	C++17	20 / 100	52 ms	38700 KB

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;
        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";
        }
        if (p->exist) {
            cout << "P" << "\n";
            have --;
        }
    }
    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

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.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct

Subtask #3
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	348 KB	Expected EOF
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Incorrect	384 KB	Expected EOF
3	Halted	0 KB	-

Subtask #5
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	348 KB	Expected EOF
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	1884 KB	Expected EOF
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	7 ms	6236 KB	Expected EOF
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	22 ms	15448 KB	Expected EOF
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	52 ms	38700 KB	Expected EOF
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	43 ms	30348 KB	Expected EOF
2	Halted	0 ms	0 KB	-