Submission #863276

#	Time	Username	Problem	Language	Result	Execution time	Memory
863276		HuyQuang_re_Zero	Type Printer (IOI08_printer)	C++14	100 / 100	134 ms	98568 KiB

printer

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 100005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define rand(l,r) (l+rng()%(r-l+1))
using namespace std;
string s,x;
int n,i,pos,sum,node;
struct trie
{
    int last,endn;
    trie *c[26];
} *u,*r;
void DFS(trie *u)
{
    if(u->endn) cout<<"P"<<'\n';
    int k=-1;
    trie *x=NULL;
    for(int i=0;i<26;i++)
        if(u->c[i]!=NULL && u->c[i]->last) k=i,x=u->c[i];
    for(int i=0;i<26;i++)
        if(u->c[i]!=NULL && u->c[i]!=x)
        {
            cout<<char(i+'a')<<'\n';
            DFS(u->c[i]);
            cout<<"-"<<'\n';
        }

    if(x!=NULL)
    {
        cout<<char(k+'a')<<'\n';
        DFS(x);
    }
    else if(u->last) exit(0);
}
int main()
{
  //  freopen("type_printer.inp","r",stdin);
  //  freopen("type_printer.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    r=new trie();
    for(i=1;i<=n;i++)
    {
        cin>>s;
        u=r;
        for(char ch:s)
        {
            if(u->c[ch-'a']==NULL) u->c[ch-'a']=new trie(),node++;
            u=u->c[ch-'a'];
        }
        u->endn=1;
        if(x.size()<s.size()) x=s,pos=i;
        sum+=s.size();
    }
    u=r;
    for(char ch:x) u=u->c[ch-'a'],u->last=1;
    cout<<2*node-x.size()+n<<'\n';
    DFS(r);
}

• 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