oj.uz

Submission #530779

# Submission time Handle Problem Language Result Execution time Memory
530779 2022-02-26T18:36:37 Z Skywk Type Printer (IOI08_printer) C++14
100 / 100
 120 ms 106416 KB 
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<math.h>
#include<queue>
#include<stack>
#include<string.h>
#define lmt 300000
#define mod 1000000007
#define pii pair<int, int>
 
using namespace std;

typedef struct trieNode
{
    bool end;
    trieNode *nxt[26];
    bool special;

    trieNode()
    {
        end=false;
        for(int i=0; i<26; i++)
            nxt[i]=NULL;
        special=false;
    }
}TtrieNode;

typedef struct trie
{
    TtrieNode root;
    vector<char> pencil;
    int op;

    trie(){
        op=0;
        root.special=true;
    }

    void insert(const string &s){
        TtrieNode *curr=&root;
        for(auto x : s){
            if(curr->nxt[x - 'a'] == NULL)
                curr->nxt[x - 'a'] = new TtrieNode;
            curr=curr->nxt[x - 'a'];
        }
        curr->end=true;
    }

    void special(const string &s){
        TtrieNode *curr=&root;
        for(auto x : s){
            curr=curr->nxt[x - 'a'];
            curr->special=true;
        }
    }

    void dfs(TtrieNode *curr){
        if(curr->end) pencil.push_back('P');
        int sp=-1;
        for(int i=0; i<26; i++)
        {
            if(curr->nxt[i] == NULL)
                continue;
            if(curr->nxt[i]->special)
                sp=i;
            else{
                pencil.push_back((char)(i + 'a'));
                dfs(curr->nxt[i]);
            }
        }  
        if(sp != -1)
        {
            pencil.push_back((char)(sp + 'a'));
            dfs(curr->nxt[sp]);
        }
        if(!curr->special) pencil.push_back('-');
    }

    void calculate()
    {
        dfs(&root);
    }

    void print()
    {
        cout<< pencil.size()<< "\n";
        for(auto x : pencil)
            cout<< x<< "\n";
    }

}Trie;

void solve()
{
    int n;
    cin>> n;

    Trie dicc;
    pair<int, string> last={0, ""}; string s;
    for(int i=0; i<n; i++)
    {
        cin>> s;
        dicc.insert(s);
        last=max(last, {s.size(), s});
    }
    dicc.special(last.second);
    dicc.calculate();
    dicc.print();
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int t=1;
    //cin>> t;

    while(t--)
    {
        solve();
        //cout<< "\n";
    }
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1868 KB Output is correct
2 Correct 3 ms 2380 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6348 KB Output is correct
2 Correct 23 ms 13380 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15688 KB Output is correct
2 Correct 7 ms 3524 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 38856 KB Output is correct
2 Correct 97 ms 89596 KB Output is correct
3 Correct 52 ms 46052 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 30396 KB Output is correct
2 Correct 120 ms 106416 KB Output is correct
3 Correct 61 ms 52384 KB Output is correct
4 Correct 101 ms 100500 KB Output is correct