제출 #531352

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
531352		jenkinsser	Type Printer (IOI08_printer)	C++17	20 / 100	64 ms	39096 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 sz;
    bool endOfWord = false;
};

typedef node* pnode;

pnode new_node(){
    pnode nd = new node;
    nd->sz = 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->sz++;
    }
    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]->sz,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: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10