제출 #1124108

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1124108		Khalid_Alabdullatif	Type Printer (IOI08_printer)	C++20	100 / 100	181 ms	50264 KiB

printer

#include <bits/stdc++.h>
#define F first
#define S second
typedef long long ll;
using namespace std;
const int N=1e6+1,mod=1e9+7;
int trie[N][26],mxd[N];
char c[N];
bool leaf[N];
int n;
int sz=0;
bool cmp(int a,int b){
    return mxd[a]<mxd[b];
}
void insert(string t){
    int node=0,siz=t.size();
    for(int i=0;i<siz;i++){
        mxd[node]=max(mxd[node],siz-i);
        if(trie[node][t[i]-'a']==0)trie[node][t[i]-'a']=++sz;
        node=trie[node][t[i]-'a'];
        c[node]=t[i];
    }
    leaf[node]=1;
}
int cnt=0;
bool stop=0;
vector<char>ans;
void dfs(int node=0){
    if(leaf[node]){
        ans.push_back('P');
        cnt++;
        if(cnt==n)
            stop=1;
    }
    sort(trie[node],trie[node]+26,cmp);
    for(int i=0;i<26;i++){
        if(!trie[node][i])continue;
        ans.push_back(c[trie[node][i]]);
        dfs(trie[node][i]);
    }
    if(!stop)
        ans.push_back('-');
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++){
        string t;
        cin>>t;
        insert(t);
    }
    dfs();
    cout<<ans.size()<<'\n';
    for(auto i:ans)
        cout<<i<<'\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