Submission #396248

#	Time	Username	Problem	Language	Result	Execution time	Memory
396248		Sundavar	Type Printer (IOI08_printer)	C++14	100 / 100	342 ms	48616 KiB

printer

#include <bits/stdc++.h>

using namespace std;

struct node{
    map<int,int> to;
    bool end = false;
    int depth = 0;
};
vector<node> graph;

void add(string& s){
    int curr = 0;
    for(char c : s){
        if(graph[curr].to.count(c-'a') == 0){
            graph[curr].to[c-'a'] = graph.size();
            graph.push_back(node());
        }
        curr = graph[curr].to[c-'a'];
    }
    graph[curr].end = true;
}

string sol;
int getDepth(int curr){
    int ans = -1;
    for(int i = 0; i < 26; i++)
        if(graph[curr].to.count(i) != 0)
            ans = max(ans, getDepth(graph[curr].to[i]));
    graph[curr].depth = ++ans;
    return ans;
}
void walk(int curr, string& s, string& ending){
    if(graph[curr].end)
        s += 'P';
    vector<pair<int,int> > to;
    for(int i = 0; i < 26; i++)
        if(graph[curr].to.count(i) != 0)
            to.push_back({graph[graph[curr].to[i]].depth, i});
    sort(to.begin(), to.end());
    for(pair<int,int>& t : to){
        s += ending; ending = "";
        s += (char)('a'+t.second);
        walk(graph[curr].to[t.second], s, ending);
    }
    ending += "-";
}

int main(){
    int n;
    cin>>n;
    graph.push_back(node());
    while(n--){
        string s;
        cin>>s;
        add(s);
    }
    string sol = "", ending = "";
    getDepth(0);
    walk(0, sol, ending);
    cout<<sol.size()<<"\n";
    for(char& a : sol)
        cout<<a<<"\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