oj.uz

Submission #825663

# Submission time Handle Problem Language Result Execution time Memory
825663 2023-08-15T06:56:19 Z taitruong270 Type Printer (IOI08_printer) C++17
100 / 100
 112 ms 113284 KB 
/*==============================================================================================================
         __                    __                                             _____     ______    _______
        |  |                  |  |                                           /  __ \   / _____|  / ______|     
      __|  |__              __|  |__                                         |_|  | |  | |       | |  
     |__|   __|            |__|   __|                                             | |  | |____   | |_____ 
        |  |    _____   _     |  |    ____  __  __  ____    _____    _____       / /   \ ___  \  |  ___  \
        |  |   /  _  \ | |    |  |   /  _/ | | | | /  _  \ /  __ \  /  _  \     / /         | |  | |   | |
        |  |_  | |_| | | |    |  |_  | |   | |_| | | |_| | | |  | | | |_| |    / /___   ____| |  | |___| |
        \____\ \____/| |_|    \____\ |_|   \_____/ \_____/ |_|  |_| \____ |   |______| |______/  \_______/
                                                                        | |
                                                                      __/ |
                                                                     |___/  
                                        Pratice, practice, and practice
                                       Where is the bug, delete it there
                                     Try, try, try again until you succeed
I hated every minute of training, but I said, 'Don't quit. Suffer now and live the rest of your life as a champion.' - Mohamed Ali 
                              You may not be the best, but must be the most effort
     Even the things and people you like, you don't have the courage to take, you are destined to be a failure.
                                           Difficult means more time
                                         Pain + Reflection = Progress 
==============================================================================================================*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define endl '\n'
const ll mod = 1e9+7;
const ll inf = 1e18;

struct Trie 
{
    struct node 
    {
        ll cnt, isEnd, mx, lst; //so tien to va so luong xau ket thuc 
        node *child[26];

        node()
        {
            cnt=0;
            isEnd=false;
            mx=-1;
            lst=-1;
            for (ll i=0; i<26; i++) child[i]=NULL;
        }
    };
    node *root=new node();
    string tmp;
    string ans;

    Trie() {}

    void insert(string s)
    {
        ll n=s.size();
        node *p=root;
        for (ll i=0; i<n; i++)
        {
            ll nxt=s[i]-'a';
            if (p->child[nxt]==NULL) p->child[nxt]=new node();
            if (n-i-1>p->mx)
            {
                p->mx=n-i-1;
                p->lst=nxt;
            }
            p=p->child[nxt];
            p->cnt+=1;
        }
        p->isEnd=1;
    }

    void dfs(node *p)
    {
        if (p->isEnd>0) ans.push_back('P');
        for (ll i=0; i<26; i++) if (p->child[i]!=NULL && i!=p->lst) 
        {
            ans.push_back(char(i+'a'));
            dfs(p->child[i]);
        }
        if (p->lst!=-1)
        {
            ans.push_back(char(p->lst+'a'));
            dfs(p->child[p->lst]);
        }
        ans.push_back('-');
    }

    void travel(node *p, string s)
    {
        if (p==NULL) return;
        cout<<s<<" "<<p->lst<<" "<<p->mx<<endl;
        for (ll i=0; i<26; i++) if (p->child[i]!=NULL) travel(p->child[i], s+char('a'+i));
    }

    void debug() { travel(root, ""); }
};

void solve()
{
    ll n; cin>>n;
    Trie trie;
    for (ll i=0; i<n; i++)
    {
        string s; cin>>s;
        trie.insert(s);
    }
    trie.dfs(trie.root);
    while (trie.ans.back()=='-') trie.ans.pop_back();
    cout<<trie.ans.size()<<endl;
    for (auto i: trie.ans) cout<<i<<endl;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    clock_t start = clock();
      //#ifndef ONLINE_JUDGE
      //freopen("_input.txt", "r", stdin);
      //freopen("_output.txt", "w", stdout);
     // #endif
    solve();
    clock_t end = clock();
    cerr<<"Time: "<<fixed<<setprecision(10)<<double(end-start)/double(CLOCKS_PER_SEC)<<"\n";
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 320 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 1236 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2004 KB Output is correct
2 Correct 2 ms 2516 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6740 KB Output is correct
2 Correct 15 ms 14252 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 16616 KB Output is correct
2 Correct 7 ms 3784 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 41448 KB Output is correct
2 Correct 112 ms 95292 KB Output is correct
3 Correct 52 ms 49056 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 32348 KB Output is correct
2 Correct 112 ms 113284 KB Output is correct
3 Correct 60 ms 55660 KB Output is correct
4 Correct 103 ms 106952 KB Output is correct