oj.uz

답안 #896724

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
896724 2024-01-02T01:56:02 Z 12345678 Type Printer (IOI08_printer) C++17
100 / 100
 153 ms 121836 KB 
#include <bits/stdc++.h>

using namespace std;

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

struct trie
{
    struct node
    {
        char c;
        int type, word;
        node* nxt[27];
        node* p;
        node(char ch, node* pa)
        {
            c=ch;
            p=pa;
            type=word=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']);
        }
        (*c)->word=1;
    }
    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;
        if (k->word) ans.push_back('P');
        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 (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';
}

/*
4
hello
hell
ell
zzz
*/

Compilation message

printer.cpp: In member function 'void trie::print(trie::pnode)':
printer.cpp:52:14: warning: variable 'pt' set but not used [-Wunused-but-set-variable]
   52 |         bool pt=0;
      |              ^~

Subtask #1
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 #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
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 #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7132 KB Output is correct
2 Correct 18 ms 15060 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 17868 KB Output is correct
2 Correct 7 ms 4060 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 44996 KB Output is correct
2 Correct 134 ms 103860 KB Output is correct
3 Correct 68 ms 53960 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 34808 KB Output is correct
2 Correct 153 ms 121836 KB Output is correct
3 Correct 78 ms 59576 KB Output is correct
4 Correct 126 ms 114604 KB Output is correct