Submission #530778

#	Time	Username	Problem	Language	Result	Execution time	Memory
530778		Skywk	Type Printer (IOI08_printer)	C++14	0 / 100	62 ms	38944 KiB

printer

#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: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10