Submission #1365284

#	Time	Username	Problem	Language	Result	Execution time	Memory
1365284		abmr59	Type Printer (IOI08_printer)	C++20	100 / 100	118 ms	105936 KiB

printer

#include<bits/stdc++.h>
using namespace std;
struct nod{
    nod *v[26];
    long long d , max_d ,ed;
    
    nod(){
        for(int i = 0 ; i < 26 ; i++) v[i] = 0;
        d = 0;
        max_d = 0;
        ed = 0;
    }
};

string ans;

nod *r = new nod;

void in(string s){
    nod *cur = r;
    for(auto c : s){
        if(!(cur -> v[c - 'a'])) cur -> v[c - 'a'] = new nod;
        cur = cur -> v[c - 'a'];
    }
    cur -> ed++;
}

void dfs_d(nod *cur){
    cur -> max_d = cur -> d; 
    for(int i = 0 ; i < 26 ; i++){
        if((cur -> v[i])){
        cur -> v[i] -> d = cur -> d + 1;
        dfs_d(cur -> v[i]);
        cur -> max_d = max(cur -> max_d , cur -> v[i] -> max_d);
        }
        
    }
   // cur -> = cur -> d + 1;
}

void dfs(nod *cur){
    long long m = -1;
    
    while(cur -> ed--){
        ans+="P";
    }
    for(int i = 0 ; i < 26 ; i++){
        if((cur -> v[i])){
            if(m == -1 || cur -> v[m] -> max_d < cur -> v[i] -> max_d) m = i;
        }
    }
    
    for(int i = 0 ; i < 26 ; i++){
        if(cur -> v[i] && i != m){
            ans+= i + 'a';
            dfs(cur -> v[i]);
            ans+="-";
        }
    }
    
    if(m != -1){
        ans+= m + 'a';
        dfs(cur -> v[m]);
        ans+="-";
    }
}
int main(){
    long long n;
    cin >> n;
    
    for(int i = 0 ; i < n ; i++){
        string s;
        cin >> s;
        in(s);
    }
    
    dfs_d(r);
    dfs(r);
    
    while(ans.back() == '-') ans.pop_back();
    cout << ans.size() << "\n";
    for(auto i : ans) cout << i << "\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