oj.uz

답안 #896723

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
896723 2024-01-02T01:51:01 Z 12345678 Type Printer (IOI08_printer) C++17
20 / 100
 56 ms 42444 KB 
#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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 456 KB didn't print every word
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 600 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2140 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 6944 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 24 ms 16844 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 55 ms 42444 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 56 ms 32900 KB didn't print every word
2 Halted 0 ms 0 KB -