Submission #388134

#	Time	Username	Problem	Language	Result	Execution time	Memory
388134		IloveN	Type Printer (IOI08_printer)	C++14	100 / 100	224 ms	89912 KiB

printer

#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(vr) vr.begin(),vr.end()
#define vi vector<int>
#define vll vector<ll>
const int N=1e5+10;

struct node
{
    map<char,node*> nxt;
    int mx_len;
    vector<pair<int,char>> order;
};

node* root=new node();

void add_string(string s)
{
    node* cur=root;
    for (char c : s)
    {
        if (cur->nxt[c]==NULL) cur->nxt[c]=new node();
        cur=cur->nxt[c];
    }
    cur->mx_len=s.length();
}

void dfs(node *cur)
{
    if (cur->nxt.empty()) return;
    cur->mx_len=0;
    vector<pair<int,char>> &vt=cur->order;
    for (pair<char,node*> p : cur->nxt)
    {
        dfs(p.se);
        cur->mx_len=max(cur->mx_len,p.se->mx_len);
        vt.eb(p.se->mx_len,p.fi);
    }
    sort(all(vt));
}

vector<char> ans;

void print(node *cur)
{
    for (pair<int,char> p : cur->order)
        if (p.se=='P') ans.eb(p.se);
        else
        {
            ans.eb(p.se);
            print(cur->nxt[p.se]);
            ans.eb('-');
        }
}

int main()
{
    //freopen("ss.inp","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        string s;
        cin>>s;
        s+='P';
        add_string(s);
    }
    dfs(root);
    print(root);
    while (ans.back()=='-') ans.pop_back();
    cout<<ans.size()<<"\n";
    for (char c : ans) cout<<c<<"\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