Submission #531354

#	Time	Username	Problem	Language	Result	Execution time	Memory
531354		jenkinsser	Type Printer (IOI08_printer)	C++17	100 / 100	134 ms	106436 KiB

printer

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pii pair<int,int>
#define piii pair<int,pii>
#define sp " "
#define nl "\n"
#define all(x) x.begin(),x.end()
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);
#define int ll
 
using namespace std;

const int N = 2e5+5;
const int INF = 1e9+5;
const int mod = 1e9+7;

struct node{
    node * letters[26];
    int max_depth;
    bool endOfWord = false;
};

typedef node* pnode;

pnode new_node(){
    pnode nd = new node;
    nd->max_depth = 0;
    nd->endOfWord = false;
    for(int i=0;i<26;i++)
        nd->letters[i] = NULL;
    return nd;
}

void insert(string s,pnode cur){
    for(char c:s){
        if(cur->letters[c-'a'] == NULL)
            cur->letters[c-'a'] = new_node();
        cur = cur->letters[c-'a'];
        cur->max_depth = max(cur->max_depth, (int)s.size());
    }
    cur->endOfWord = true;
}

string ans;

void dfs(pnode v){
    if(v->endOfWord)
        ans += "P";
    vector<pii> order;
    for(int i = 0; i < 26; i++){
        if(v->letters[i] != NULL)
            order.pb({v->letters[i]->max_depth,i});
    }
    sort(all(order));
    for(auto [x,c]:order){
        ans += (char)(c+'a');
        dfs(v->letters[c]);
        ans += '-';
    }
}

int n;

void solve(){
    cin >> n;
    pnode root = new_node();
    for(int i=1;i<=n;i++){
        string s;
        cin >> s;
        insert(s,root);
    }
    dfs(root);
    while(!ans.empty() && ans.back()!='P')
        ans.pop_back();
    cout << ans.size() << nl;
    for(char c:ans)
        cout << c << nl;
}

signed main(){
    #ifdef LOCAL
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
        
    fastio()

    int tt=1;
    // cin >> tt;
    while(tt--)
        solve();
    
    #ifdef LOCAL
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

• 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