Submission #1256144

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256144		minhpk	Type Printer (IOI08_printer)	C++20	100 / 100	88 ms	52924 KiB

printer

#include <bits/stdc++.h>

using namespace std;
int child[2000005][26];
int isend[2000005];
int cnt=0;
int par[2000005];
int low[2000005];
vector <char> v;

void rev(int k){
    int pre=1;
    while (k>0){
         low[k]=max(low[k],pre);
         k=par[k];
         pre++;
    }
}

void add(string s){
    int k=0;
    for (auto c:s){
        if (child[k][c-'a']==0){
            cnt++;
            child[k][c-'a']=cnt;
            par[cnt]=k;
        }
        k=child[k][c-'a'];
    }
    isend[k]++;
    rev(k);
}


void get(int k){
    for (int i=1;i<=isend[k];i++){
         v.push_back('P');
    }
    int trace=-1,max1=0;
    for (int i=0;i<=25;i++){
         if (child[k][i]){
             if (max1<low[child[k][i]]){
                 max1=low[child[k][i]];
                 trace=i;
             }
         }
    }
    for (int i=0;i<=25;i++){
         if (child[k][i] && i!=trace){
             v.push_back(char(i+'a'));
             get(child[k][i]);
             v.push_back('-');
         }
    }

    if (trace!=-1){
        v.push_back(char(trace+'a'));
        get(child[k][trace]);
        v.push_back('-');
    }
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a;
    cin >> a;
    for (int i=1;i<=a;i++){
         string s;
         cin >> s;
         add(s);
    }

    get(0);
    while (v.back()=='-'){
          v.pop_back();
    }
    cout << v.size() << "\n";
    for (auto c:v){
        cout << c<<"\n";
    }

    return 0;
}

• 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