Submission #1018235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018235		Mardonbekhazratov	Type Printer (IOI08_printer)	C++17	100 / 100	76 ms	48736 KiB

printer

#include<bits/stdc++.h>
using namespace std;

const int mxN=5e5+5;
int trie[mxN][26];
int node_cnt = 0;
bool stop[mxN];
vector<char>ans;
string longest;

void insert(string&s){
    int node=0;
    for(char c:s){
        if(trie[node][c-'a']==0) trie[node][c-'a']=++node_cnt;
        node=trie[node][c-'a'];
    }
    stop[node]=true;
}

void dfs(int node,int depth){
    if(stop[node]) ans.push_back('P');
    bool ok=false;
    for(int i=0;i<26;i++){
        if(trie[node][i]!=0 && i==longest[depth]-'a'){
            ok=true;
            continue;
        }
        if(trie[node][i]==0) continue;
        ans.push_back(char(i+'a'));
        dfs(trie[node][i],depth+1);
        ans.push_back('-');
    }
    if(ok){
        ans.push_back(longest[depth]);
        dfs(trie[node][longest[depth]-'a'],depth+1);
        ans.push_back('-');
    }
}

signed main(){
    int n;
    cin>>n;
    longest="";
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        insert(s);
        if(s.size()>longest.size()) swap(longest,s);
    }
    dfs(0,0);
    while(ans.back()=='-') ans.pop_back();
    cout<<ans.size()<<'\n';
    for(char c:ans) cout<<c<<'\n';
}

• 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