제출 #1195126

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195126		KindaGoodGames	Type Printer (IOI08_printer)	C++20	100 / 100	153 ms	69104 KiB

printer

#include<bits/stdc++.h>

#define ll long long
#define pii pair<int,int>
#define tiii tuple<int,int,int>

using namespace std;

struct TrieNode{
    bool marked;
    int depth = 0;
    int height = 0;
    vector<int> child;
    TrieNode(){
        child.resize(26, -1);
        marked = false;
    }
};

vector<TrieNode> trie;
int cnt = 0;
string res = "";

void insert(string& s, int i = 0, int ind = 0){
    if(i == s.size()){
        trie[ind].marked = true;
        return;
    }

    int c = trie[ind].child[s[i]-'a'];
    if(c == -1){
        trie[ind].child[s[i]-'a'] = trie.size();
        trie.push_back(TrieNode());
        c = trie[ind].child[s[i]-'a'];
        trie[c].depth = trie[ind].depth+1; 
    } 

    insert(s,i+1,c);
    trie[ind].height = max(trie[c].height+1, trie[ind].height);
}

void add(char c){
    res += c; 
    cnt++;
}
void trav(int ind = 0){  
    if(trie[ind].marked){
        add('P'); 
    }
    vector<tiii> choices;
    for(int i = 0; i < 26; i++){
        int c = trie[ind].child[i];
        if(c == -1){
            continue;
        }
        choices.push_back({trie[c].height, c, i});
    }

    sort(choices.begin(),choices.end());
    for(auto p : choices){
        int h,c,i;
        tie(h,c,i) = p;
        add('a'+i);
        trav(c);
        add('-');
    }
}
int main(){
    trie.push_back(TrieNode());

    int n;
    cin >> n;

    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        insert(s);
    }

    trav(0);

    while(res.back() == '-'){
        res.pop_back();
        cnt--;
    }
    cout << cnt <<endl;
    for(int i = 0; i < res.size(); i++){
        cout << res[i] << "\n";
    }
}

• 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