제출 #1158264

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1158264		AlgorithmWarrior	Type Printer (IOI08_printer)	C++20	100 / 100	170 ms	43944 KiB

printer

#include <bits/stdc++.h>

using namespace std;

struct node
{
    vector<pair<int,node*>>child;
    int cuv;
    node* longest;
    int maxim;
    node(int nr)
    {
        longest=0;
        maxim=0;
        cuv=0;
    }
};
node *root=new node(0);
string rasp;

node* fp(node* nod,int nr)
{
    for(auto per : nod->child)
        if(per.first==nr)
            return per.second;
    return 0;
}

void adauga(string word,int ind,node* nod)
{
    if(word.size()>ind)
    {
        int urm=word[ind]-'a';
        if(!fp(nod,urm))
            nod->child.push_back({urm,new node(0)});
        adauga(word,ind+1,fp(nod,urm));
    }
    else
        if(word.size()==ind)
            ++nod->cuv;
}

void dfs0(node* nod)
{
    int i;
    for(i=0;i<26;++i)
        if(fp(nod,i))
        {
            dfs0(fp(nod,i));
            if(fp(nod,i)->maxim>nod->maxim)
            {
                nod->maxim=fp(nod,i)->maxim;
                nod->longest=fp(nod,i);
            }
        }
    ++nod->maxim;
}

void dfs(node* nod)
{
    while(nod->cuv--)
        rasp.push_back('P');
    if(nod->longest){
    int i;
    char lit;
    for(i=0;i<26;++i)
        if(fp(nod,i))
            if(fp(nod,i)==nod->longest)
                lit=i;
            else
            {
                rasp.push_back(i+'a');
                dfs(fp(nod,i));
            }
    rasp.push_back(lit+'a');
    dfs(nod->longest);}
    rasp.push_back('-');
}

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        string s;
        cin>>s;
        adauga(s,0,root);
    }
    dfs0(root);
    dfs(root);
    while(rasp.back()=='-')
        rasp.pop_back();
    cout<<rasp.size()<<'\n';
    for(auto ch : rasp)
        cout<<ch<<'\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