oj.uz

Submission #530777

# Submission time Handle Problem Language Result Execution time Memory
530777 2022-02-26T18:24:11 Z Skywk Type Printer (IOI08_printer) C++14
0 / 100
 43 ms 38844 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;
    }

    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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 332 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 332 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1868 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 6304 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 15668 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 38844 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 30388 KB Expected EOF
2 Halted 0 ms 0 KB -