oj.uz

Submission #1069033

# Submission time Handle Problem Language Result Execution time Memory
1069033 2024-08-21T14:54:05 Z nhanhoang510 Type Printer (IOI08_printer) C++14
100 / 100
 100 ms 100688 KB 
#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

const int maxn = 25000 + 7;
const int LOG = 20;
const long long MOD = (long long)(1e9) + 7;
const long long base = 311;
const int ALP_BET = 26;

typedef pair<int, int> ii;
typedef pair<int, long long> il;
typedef pair<long long, int> li;
typedef pair<long long, long long> ll;

struct Trie_Node{
    bool Print;
    bool Spec;
    Trie_Node* node[ALP_BET];
};

Trie_Node* create_node(){
    Trie_Node* node = new Trie_Node;
    for(int i = 0; i < ALP_BET; ++i)
        node->node[i] = NULL;
    node->Print = false;
    node->Spec = false;
    return node;
}

int n;
string s[maxn];

int num_node = 0;

void add(Trie_Node* root, int id, bool op){
    int m = s[id].size();
    for(int i = 0; i < m; ++i){
        int c = int(s[id][i]) - int('a');
        if(root->node[c] == NULL){
            root->node[c] = create_node();
            ++num_node;
        }
        root = root->node[c];
        if(op == true)
            root->Spec = true;
    }
    root->Print = true;
    return;
}

void dfs(Trie_Node* node){
    if(node->Print == true)
        cout << "P\n";
    for(int c = 0; c < ALP_BET; ++c) if(node->node[c] != NULL && node->node[c]->Spec == false){
        cout << char(c + int('a')) << "\n";
        dfs(node->node[c]);
    }
    for(int c = 0; c < ALP_BET; ++c) if(node->node[c] != NULL && node->node[c]->Spec == true){
        cout << char(c + int('a')) << "\n";
        dfs(node->node[c]);
    }
    if(node->Spec == false)
        cout << "-\n";
    return;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    int max_len = 0;
    for(int i = 1; i <= n; ++i){
        cin >> s[i];
        max_len = max(max_len, int(s[i].size()));
    }
    bool build_spec = false;
    Trie_Node* root = create_node();
    num_node = 0;
    for(int i = 1; i <= n; ++i) if(int(s[i].size()) != max_len || build_spec == true){
        add(root, i, false);
    } else{
        build_spec = true;
        add(root, i, true);
    }
    cout << num_node * 2 - max_len + n << "\n";
    root->Spec = true;
    dfs(root);
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1880 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 15452 KB Output is correct
2 Correct 6 ms 4188 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 37212 KB Output is correct
2 Correct 82 ms 84564 KB Output is correct
3 Correct 51 ms 44628 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 29012 KB Output is correct
2 Correct 100 ms 100688 KB Output is correct
3 Correct 46 ms 50516 KB Output is correct
4 Correct 84 ms 95060 KB Output is correct