제출 #1069033

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1069033		nhanhoang510	Type Printer (IOI08_printer)	C++14	100 / 100	100 ms	100688 KiB

printer

#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 / 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