oj.uz

답안 #896722

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

using namespace std;

int n, cnt;
string s;

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) cout<<(char)('a'+i)<<'\n', pt=1, print(k->nxt[i]);
        for (int i=0; i<27; i++) if (k->nxt[i]&&k->nxt[i]->type==1) cout<<(char)('a'+i)<<'\n', pt=1, print(k->nxt[i]);
        if (!pt) cout<<"P\n";
        if (k->type) return;
        cout<<"-\n";
    }
} 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);
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Expected integer, but "t" found
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Expected integer, but "e" found
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Expected integer, but "h" found
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Expected integer, but "b" found
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 604 KB Expected integer, but "a" found
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 2140 KB Expected integer, but "a" found
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 6880 KB Expected integer, but "a" found
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 22 ms 16572 KB Expected integer, but "a" found
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 61 ms 43212 KB Expected integer, but "a" found
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 50 ms 32440 KB Expected integer, but "a" found
2 Halted 0 ms 0 KB -