Submission #546213

#	Time	Username	Problem	Language	Result	Execution time	Memory
546213		perchuts	Type Printer (IOI08_printer)	C++17	100 / 100	157 ms	105916 KiB

printer

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;

const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 1e5+100;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

struct trie{
    trie *alpha[27], *parent;
    bool later, isEnd;
    trie(trie *p){
        for(int i=0;i<27;++i)alpha[i] = nullptr;
        later = 0, parent = p, isEnd = 0;
    }
}*Trie;

int mx;
trie *deepest;
void dfs(trie *cur, int height){
    if(ckmax(mx,height))deepest = cur;
    for(int i=0;i<26;++i){
        if(cur->alpha[i]!=nullptr){
            dfs(cur->alpha[i],height+1);
        }
    }
}
vector<char>ans;

void dfs2(trie *cur){
    int last = -1;
    if(cur->isEnd==1)ans.pb('P');
    for(int i=0;i<26;++i){
        if(cur->alpha[i]!=nullptr){
            if(cur->alpha[i]->later==1)last = i;
            else{
                ans.pb(char('a'+i));
                dfs2(cur->alpha[i]);
            }
        }
    }
    if(last!=-1){
        ans.pb(char('a'+last));
        dfs2(cur->alpha[last]);
    }
    if(cur->later==0)ans.pb('-');
}

int main(){_
    int n;cin>>n;
    Trie = new trie(nullptr);
    for(int i=1;i<=n;++i){
        string s;cin>>s;
        trie *cur = Trie;
        for(auto x:s){
            int ch = x - 'a';
            if(cur->alpha[ch]==nullptr)cur->alpha[ch] = new trie(cur);
            cur = cur->alpha[ch];
        }
        cur->isEnd = 1;
    }
    dfs(Trie, 1);
    while(deepest!=nullptr){
        deepest->later = 1, deepest = deepest->parent;
    }
    dfs2(Trie);
    cout<<sz(ans)<<endl;
    for(auto x:ans)cout<<x<<endl;
}

• 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