Submission #393899

#	Time	Username	Problem	Language	Result	Execution time	Memory
393899		AmineTrabelsi	Type Printer (IOI08_printer)	C++14	100 / 100	193 ms	62648 KiB

printer

#include <bits/stdc++.h>
using namespace std;
// Hi 
int n;
vector<vector<int>> Trie;
vector<bool> last,marked;
vector<int> vv;
void add(string s){
    int curr = 0;
    for(auto x:s){
        int c = x-'a';
        if(Trie[curr][c] == -1){
            Trie[curr][c] = Trie.size();
            Trie.push_back(vv);
            last.push_back(0);
            marked.push_back(0);
        }
        curr = Trie[curr][c];
    }
    last[curr] = 1;
}
void mark(string s){
    int curr = 0;
    for(auto x:s){
        int c = x-'a';
        marked[Trie[curr][c]] = 1;
        curr = Trie[curr][c];
    }
}
vector<char> ops;
void dfs(int curr){
    vector<int> left;
    for(int c=0;c<26;c++){
        if(Trie[curr][c] == -1)continue;
        if(marked[Trie[curr][c]])left.push_back(c);
        else {
            ops.push_back(c+'a');
            dfs(Trie[curr][c]);
            ops.push_back('-');
        }
    }
    for(auto c:left){
        if(last[curr])ops.push_back('P');
        ops.push_back(c+'a');
        dfs(Trie[curr][c]);
    }
    if(last[curr] && !marked[curr])ops.push_back('P');
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    for(int i=0;i<26;i++)vv.push_back(-1);
    cin>>n;
    string w;
    string longest = "";
    Trie.push_back(vv);
    last.push_back(0);
    marked.push_back(0);
    for(int i=0;i<n;i++){
        cin>>w;
        add(w);
        if(w.size() > longest.size()){
            longest = w;
        }
    }

    mark(longest); // mark the longest word to keep the last
    dfs(0);
    cout << ops.size() +1 <<'\n';
    for(auto c:ops)cout<<c<<'\n';
        cout<<'P'<<'\n';
    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