제출 #1261787

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1261787		vhaohao	Type Printer (IOI08_printer)	C++20	10 / 100	124 ms	88996 KiB

printer

#include<bits/stdc++.h>
using namespace std;
#define mask(n) (1LL<<(n))
#define checkBit(bit,n) ((n) & mask(bit))
#define flipBit(bit,n) ((n) ^ mask(bit))
#define cntBit(n) __builtin_popcount(n)
#define fastIO ios_base::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
#define ll long long
#define repu(i,a,b)  for(int i=a;i<=b;i++)
#define repd(i,a,b)  for(int i=a;i>=b;i--)
// const int N=;

struct Trie{
    struct Node
    {
        Node* child[26];
        int cnt,exist,miLen;
        Node(){
            for (int i=0;i<26;i++)
                child[i]=NULL;
            
            exist=cnt=0;
            miLen=30;
        }
    };

    Node* root;
    Trie(){
        root=new Node();
    }

    void add_string(Node*p,string s,int i){
        if (i!=s.size()){
            int c=s[i]-'a';
            if (p->child[c]==NULL) p->child[c]=new Node();
            p->child[c]->cnt++;
            p->miLen = min(p->miLen, int(s.size()));
            add_string(p->child[c],s,i+1);
        }
        else {
            p->exist++;
            p->miLen = min(p->miLen, int(s.size()));
        }
    }

    bool delete_string_recursive(Node* p,string s,int i){
        if (i!=s.size()){
            int c=s[i]-'a';
            bool is_child_deleted=delete_string_recursive(p->child[c],s,i+1);
            
            if (is_child_deleted) p->child[c]=NULL;
        }
        else p->exist--;

        if (p!=root){
            p->cnt--;
            if (p->cnt==0){
                delete(p);
                return true;
            }

        }
        
        return false;
    }

    void delete_string(string s){
        if (!find_string(s)) return;
        delete_string_recursive(root,s,0);

    }

    bool find_string(string s){
        Node *p=root;

        for (auto f:s){
            int c=f-'a';

            if (p->child[c]==NULL) return 0;

            p=p->child[c];
        }

        return (p->exist!=0);
    }

    string res="";

    void typing(Node* p){
        vector<pair<int,int>> miNode;

        repu(c,0,25)
            if (p->child[c] != NULL)
                miNode.push_back({p->child[c]->miLen, c});

        sort(miNode.begin(),miNode.end());
        
        repu(i,1,p->exist) res+='P';


        for (pair<int,int> x:miNode)
            {
                res+=char(x.second+'a');
                typing(p->child[x.second]);
                res+='-';
            }
        

        if (p==root){
            while (res[res.size()-1]=='-') res.pop_back();
            cout<<res.size()<<"\n";
            // cout<<res;
            repu(i,0,res.size()-1) cout<<res[i]<<"\n";
        }
    }
};

int main()
{
    // fastIO   
    int n;
    cin>>n;

    Trie *tr=new Trie();
    repu(i,1,n){
        string tmp;
        cin>>tmp;
        tr->add_string(tr->root,tmp,0);
    }

    tr->typing(tr->root);
}

• Subtask 1: 10 / 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