oj.uz

Submission #993893

# Submission time Handle Problem Language Result Execution time Memory
993893 2024-06-06T18:36:17 Z May27_th Type Printer (IOI08_printer) C++17
100 / 100
 130 ms 105552 KB 
#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

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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 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
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1884 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6236 KB Output is correct
2 Correct 19 ms 13144 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 15448 KB Output is correct
2 Correct 6 ms 3420 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 38480 KB Output is correct
2 Correct 116 ms 88660 KB Output is correct
3 Correct 60 ms 45652 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 30032 KB Output is correct
2 Correct 130 ms 105552 KB Output is correct
3 Correct 70 ms 51796 KB Output is correct
4 Correct 116 ms 99580 KB Output is correct