Submission #896723

#	Time	Username	Problem	Language	Result	Execution time	Memory
896723		12345678	Type Printer (IOI08_printer)	C++17	20 / 100	56 ms	42444 KiB

printer

#include <bits/stdc++.h>

using namespace std;

int n, cnt;
string s;
vector<char> ans;

struct trie
{
    struct node
    {
        char c;
        int type;
        node* nxt[27];
        node* p;
        node(char ch, node* pa)
        {
            c=ch;
            p=pa;
            type=0;
            for (int i=0; i<27; i++) nxt[i]=NULL;
        }
    };
    typedef node* pnode;
    pnode rt=new node('a', NULL);
    vector<pair<int, pnode>> v;
    void update(string &s)
    {
        pnode* c=&rt;
        for (auto x:s)
        {
            if ((*c)->nxt[x-'a']) c=&((*c)->nxt[x-'a']);
            else (*c)->nxt[x-'a']=new node(x, *c), c=&((*c)->nxt[x-'a']);
        }
    }
    void dfssz(pnode k, int lvl)
    {
        v.push_back({lvl, k});
        for (int i=0; i<27; i++) if (k->nxt[i]) dfssz(k->nxt[i], lvl+1);
    }
    void calcheavy()
    {
        pair<int, pnode> t;
        for (auto x:v) t=max(t, x);
        //cout<<t.first<<' '<<t.second->c<<'\n';
        while (t.second!=NULL) t.second->type=1, t.second=t.second->p;
    }
    void print(pnode k)
    {
        bool pt=0;
        for (int i=0; i<27; i++) if (k->nxt[i]&&k->nxt[i]->type!=1) ans.push_back('a'+i), pt=1, print(k->nxt[i]);
        for (int i=0; i<27; i++) if (k->nxt[i]&&k->nxt[i]->type==1) ans.push_back('a'+i), pt=1, print(k->nxt[i]);
        if (!pt) ans.push_back('P');
        if (k->type) return;
        ans.push_back('-');
    }
} d;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    while (n--) cin>>s, d.update(s);
    d.dfssz(d.rt, 0);
    d.calcheavy();
    d.print(d.rt);
    cout<<ans.size()<<'\n';
    for (auto x:ans) cout<<x<<'\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10