Submission #855866

#	Time	Username	Problem	Language	Result	Execution time	Memory
855866		GoldLight	Type Printer (IOI08_printer)	C++17	100 / 100	144 ms	99708 KiB

printer

#include <bits/stdc++.h>
using namespace std;
void fast(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);}

struct trie{
    int val; bool word;
    trie *ch[26];
    trie(){
        val=0, word=0;
        for(int i=0; i<26; i++) ch[i]=NULL;
    }
}root;
void add(string &s){
    trie *now=&root;
    for(int i=0; i<(int)s.size(); i++){
        if(!now->ch[s[i]-'a']) now->ch[s[i]-'a']=new trie();
        now=now->ch[s[i]-'a'];
    }
    now->word=1;
}
void dfs(trie *now){
    trie *next;
    for(int i=0; i<26; i++){
        if(now->ch[i]){
            next=now->ch[i];
            dfs(next);
            now->val=max(now->val, next->val);
        }
    }
    now->val++;
}
vector<char> v;
void dfs2(trie *now){
    trie *next;
    int c=27, maxn=0;
    if(now->word) v.push_back('P');
    for(int i=0; i<26; i++){
        if(now->ch[i]){
            next=now->ch[i];
            if(next->val>maxn){
                maxn=next->val;
                c=i;
            }
        }
    }
    for(int i=0; i<26; i++){
        if(now->ch[i] && i!=c){
            v.push_back(char('a'+i));
            dfs2(now->ch[i]);
        }
    }
    if(maxn){
        v.push_back(char('a'+c));
        dfs2(now->ch[c]);
    }
    v.push_back('-');
}
int main(){
    fast();
    int n; cin>>n;
    for(int i=1; i<=n; i++){
        string s; cin>>s; add(s);
    }
    dfs(&root);
    dfs2(&root);
    while(!v.empty() && v.back()=='-') v.pop_back();
    cout<<v.size()<<'\n';
    for(auto i:v) cout<<i<<'\n';
}
/*
struct trie{
    trie *ch[26];
    trie(){
        for(int i=0; i<26; i++) ch[i]=NULL;
    }
}root[2];
void add(string &s, int k){
    trie *now=&root[k];
    for(int i=0; i<(int)s.size(); i++){
        if(!now->ch[s[i]-'a']) now->ch[s[i]-'a']=new trie();
        now=now->ch[s[i]-'a'];
    }
}
bool dfs(trie *a, trie *b, int k){
    bool ans;
    if(k&1){
        ans=0;
        for(int i=0; i<26; i++){
            if(a->ch[i] && b->ch[i]) ans|=dfs(a->ch[i], b->ch[i], k+1);
            else if(a->ch[i]){
                ans=1;
                break;
            }
        }
    }
    else{
        ans=1;
        for(int i=0; i<26; i++){
            if(a->ch[i] && b->ch[i]) ans&=dfs(a->ch[i], b->ch[i], k+1);
            else if(b->ch[i]){
                ans=0;
                break;
            }
        }
    }
    return ans;
}
int main(){
    fast();
    int n; cin>>n;
    for(int i=1; i<=n; i++){
        string s; cin>>s; add(s, 0);
    }
    int m; cin>>m;
    for(int i=1; i<=m; i++){
        string s; cin>>s; add(s, 1);
    }
    if(dfs(&root[0], &root[1], 1)) cout<<"Nina";
    else cout<<"Emilija";
}
*/
/*
struct trie{
    bool val;
    trie *ch[26];
    trie(){
        val=0;
        for(int i=0; i<26; i++) ch[i]=NULL;
    }
}root;
void add(string &s){
    trie *now=&root;
    for(int i=0; i<(int)s.size(); i++){
        if(!now->ch[s[i]-'a']) now->ch[s[i]-'a']=new trie();
        now=now->ch[s[i]-'a'];
    }
    now->val=1;
}
int main(){
    fast();
    int n, m; cin>>n>>m;
    string s; cin>>s;
    for(int i=1; i<=m; i++){
        string t; cin>>t; add(t);
    }
    string t="";
    int ans=0;
    trie *now=&root;
    for(int i=0; i<n; i++){
        if(!now->ch[s[i]-'a']){
            t.clear();
            now=&root;
        }
        if(now->ch[s[i]-'a']){
            now=now->ch[s[i]-'a'];
            if(now->val){
                ans++;
                t.clear();
                now=&root;
            }
            else t+=s[i];
        }
    }
    cout<<ans;
}
*/
/*
#define int long long
const int N=5e3, NN=1e6, mod=1e9+7;
int dp[N+1];
struct trie{
    bool val;
    trie *ch[26];
    trie(){
        val=0;
        for(int i=0; i<26; i++) ch[i]=NULL;
    }
}root;
void add(string &s){
    trie *now=&root;
    for(int i=(int)s.size()-1; i>=0; i--){
        if(!now->ch[s[i]-'a']) now->ch[s[i]-'a']=new trie();
        now=now->ch[s[i]-'a'];
    }
    now->val=1;
}
vector<int> v;
void f(string &s){
    trie *now=&root;
    for(int i=(int)s.size()-1; i>=0; i--){
        int c=s[i]-'a';
        if(!now->ch[c]) return;
        now=now->ch[c];
        if(now->val) v.push_back(i);
    }
}
// int now=1, trie[NN+1][26], exi[NN+1], word[NN+1];
// void add(string &s){
//     int id=0;
//     for(int i=s.size()-1; i>=0; i--){
//         if(!exi[trie[id][s[i]-'a']]){
//             trie[id][s[i]-'a']=now++;
//             exi[now-1]=1;
//         }
//         id=trie[id][s[i]-'a'];
//     }
//     word[id]=1;
// }
// vector<int> v;
// void f(string &s){
//     int id=0;
//     for(int i=s.size()-1; i>=0; i--){
//         if(!exi[trie[id][s[i]-'a']]) return;
//         id=trie[id][s[i]-'a'];
//         if(word[id]) v.push_back(i);
//     }
// }
signed main(){
    fast();
    string s; cin>>s;
    int n=(int)s.size(), k; cin>>k;
    for(int i=1; i<=k; i++){
        string t; cin>>t; add(t);
    }
    string t="";
    dp[0]=1;
    for(int i=1; i<=n; i++){
        t+=s[i-1];
        v.clear();
        f(t);
        for(auto j:v) dp[i]+=dp[j];
        dp[i]%=mod;
    }
    cout<<dp[n];
    //for(int i=0; i<=n; i++) cout<<dp[i]<<' ';
}
*/

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10