제출 #1210257

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1210257		Warinchai	Type Printer (IOI08_printer)	C++20	100 / 100	222 ms	169784 KiB

printer

#include<bits/stdc++.h>
using namespace std;
string s[25005];
struct node{
    node *to[30];
    int l[30];
    int ll;
    int cnt;
    node(){
        for(int i=0;i<30;i++)to[i]=NULL,l[i]=0;
        cnt=0;
        ll=0;
    }
};
typedef node* pnode;
pnode rt=NULL;
vector<char>ans;
int tot=0;
int n;
int dfsl(pnode x){
    int mx=0;
    for(int i=0;i<26;i++){
        if(x->to[i]){
            x->l[i]=dfsl(x->to[i]);
            if(x->l[i]>x->l[x->ll])x->ll=i;
            mx=max(mx,x->l[i]);
        }
    }
    return mx+1;
}
void dfs(pnode x){
    for(int i=0;i<x->cnt;i++)ans.push_back('P'),tot++;
    for(int i=0;i<26;i++){
        if(i==x->ll)continue;
        if(x->to[i]){
            ans.push_back((char)(i+'a'));
            dfs(x->to[i]);
            ans.push_back('-');
        }
    }
    if(x->to[x->ll]){
        ans.push_back((char)(x->ll+'a'));
        dfs(x->to[x->ll]);
        if(tot!=n)ans.push_back('-');
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>s[i];
    pnode rt=new node();
    for(int i=1;i<=n;i++){
        string temp=s[i];
        pnode cur=rt;
        for(char x:temp){
            int val=x-'a';
            if(!cur->to[val])cur->to[val]=new node();
            cur=cur->to[val];
        }
        cur->cnt++;
    }
    dfsl(rt);
    dfs(rt);
    cout<<ans.size()<<"\n";
    for(auto x:ans)cout<<x<<"\n";
}

• 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