Submission #1365223

#	Time	Username	Problem	Language	Result	Execution time	Memory
1365223		shrimb	Type Printer (IOI08_printer)	C++20	100 / 100	115 ms	105960 KiB

printer

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct node{
    node *adj[26];
    int dep, maxdep, newend;
    
    node()
    {
        for(int i = 0; i < 26; i++)
        {
            adj[i]=0;
        } maxdep=dep=0;
    }
};

node *root = new node;

void insert(string s)
{
    node *cur = root;
    for(auto c : s)
    {
        if(!cur -> adj[c-'a']) 
        {
            cur->adj[c-'a'] = new node;
        }
        cur = cur->adj[c-'a'];
    }
    cur->newend++;
}

void dfs1(node *cur)
{
    cur -> maxdep = cur -> dep;
    for(int i = 0; i < 26; i++)
    {
        if(cur -> adj[i])
        {
            cur->adj[i]->dep = cur->dep+1;
            dfs1(cur->adj[i]);
            cur->maxdep = max(cur->maxdep, cur->adj[i]->maxdep);
        }
    }
}
string ans;
void dfs2(node *cur)
{
    while(cur->newend--) ans+='P';
    int m = -1;
    for(int i =0 ; i < 26; i++)
    {
        if(cur->adj[i])
        {
            if(m==-1 || cur->adj[m]->maxdep < cur->adj[i]->maxdep) m = i;
        }
    }
    for(int i = 0; i < 26; i++)
    {
        if(cur->adj[i]&&i!=m)
        {
            ans+=i+'a';
            dfs2(cur->adj[i]);
            ans+='-';
        }
    }
    if(m!=-1)
    {
        ans+=m+'a';
        dfs2(cur->adj[m]);
        ans+='-';
    }
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n; cin>>n;
    for(int i = 0; i < n; i++) {
        string s; cin>>s; insert(s);
    }
    dfs1(root);    
    dfs2(root);
    while(ans.back()=='-') ans.pop_back();
    cout<<ans.size()<<"\n";
    for(auto 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