Submission #1279438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279438		Zone_zonee	Type Printer (IOI08_printer)	C++20	100 / 100	274 ms	138896 KiB

printer

#include <bits/stdc++.h>
using namespace std;

int edges_cnt;
map<string, bool> mp;
struct trie_node{
    trie_node* v[26];
    char val;
    int depth;
    trie_node(char _val) : val(_val){
        for(int i = 0; i < 26; ++i) v[i] = nullptr;
    }
};
trie_node* head = new trie_node('.');
void add(string s, trie_node* now){
    for(char c : s){
        if(now->v[c-'a'] == nullptr) now->v[c-'a'] = new trie_node(c);
        now = now->v[c-'a'];
    }
}
void dfs(trie_node* now){
    int mx = 0;
    for(int i = 0; i < 26; ++i){
        if(now->v[i] != nullptr){
            edges_cnt++;
            dfs(now->v[i]);
            mx = max(mx, now->v[i]->depth);
        }
    }
    now->depth = mx+1;
}
vector<char> ans;
void print(trie_node* now, string s){
    int cnt = 0;
    for(int i = 0; i < 26; ++i){
        cnt += (now->v[i] != nullptr);
    }
    if(now->val != '.')ans.push_back(now->val);
    if(mp[s+now->val])ans.push_back('P');
    while(cnt){
        int mn = 1e9, idx = -1;
        for(int i = 0; i < 26; ++i){
            if(now->v[i] == nullptr) continue;
            if(mn > now->v[i]->depth){
                mn = now->v[i]->depth;
                idx = i;
            }
        }
        cnt--;
        if(now->val == '.')print(now->v[idx], s);
        else print(now->v[idx], s + now->val);
        now->v[idx] = nullptr;
    }
    ans.push_back('-');
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for(int i = 0; i < n; ++i){
        string s;
        cin >> s;
        mp[s] = 1;
        add(s, head);
    }
    dfs(head);
    cout << 2*edges_cnt-head->depth+n+1 << '\n';
    print(head, "");
    while(ans.back() == '-') ans.pop_back();
    for(char c : ans) cout << c << '\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