제출 #1365243

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1365243		shrimb	Type Printer (IOI08_printer)	C++20	100 / 100	438 ms	105912 KiB

printer

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


struct node{
    node *adj[26];
    int def,maxdef,en;
    
    
    node()
    {
        for( int i=0;i<26;i++)
        {
            adj[i]=0;
        }
        def=0;
        maxdef=0;
        en=0;
    }
};

node *root= new node;

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



void df1(node *cur)
{
    cur->maxdef=cur->def;
    
    for(int i=0;i<26;i++)
    {
        if(cur->adj[i])
        {
            cur->adj[i]->def=cur->def+1;
            df1(cur->adj[i]);
            cur->maxdef=max(cur->maxdef,cur->adj[i]->maxdef);
            
        }
    }
}

string ans;

void df2(node *cur)
{

    while(cur->en--)
    {
        ans+='P';
    }
    
    
    
    int m=-1;
    
    for(int i=0;i<26;i++)
    {
        if(cur->adj[i]){
            if(m==-1||cur->adj[m]->maxdef<cur->adj[i]->maxdef)
            {
                m=i;
            }
        }
    }
    
    
    
    for(int i=0;i<26;i++)
    {
        if(cur->adj[i])
        {
            if(i!=m)
            {
                ans+=i+'a';
                df2(cur->adj[i]);
                ans+='-';
            }
        }
    }
    
    if(m!=-1)
    {
        ans+=m+'a';
        df2(cur->adj[m]);
        ans+='-';
    }
    
    
}




signed main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        string t;
        cin>>t;
        insert(t);
    }
    
    df1(root);
    
    df2(root);
    
    while(ans.back()=='-') ans.pop_back();
    
    cout<<ans.size()<<endl;
    
    for(int i=0;i<ans.size();i++)
    {
        cout<<ans[i]<<endl;
    }
    
    
}

• 서브태스크 1: 10 / 10
• 서브태스크 2: 10 / 10
• 서브태스크 3: 10 / 10
• 서브태스크 4: 10 / 10
• 서브태스크 5: 10 / 10
• 서브태스크 6: 10 / 10
• 서브태스크 7: 10 / 10
• 서브태스크 8: 10 / 10
• 서브태스크 9: 10 / 10
• 서브태스크 10: 10 / 10