Submission #1175624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175624		bassmala_abood	Type Printer (IOI08_printer)	C++20	100 / 100	164 ms	69632 KiB

printer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset tree <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
#define pb push_back
#define F first
#define S second
#define all(a)  a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define sz(x) ((int)(x).size())
#define ll long long
//#define int ll
#define popcount(x) __builtin_popcountll(x)
//__builtin_clzll()->leading zeros in binary
#define inf 1e18
#define el "\n"
#define Bassmala ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
vector<int> take(int n){
    vector<int>v(n);
    for(int i=0;i<n;i++)cin>>v[i];
    return v;
}

//--------------------------------global variables----------------------------------//
string ans;
const int sz=26;
//---------------------------------functions----------------------------------------//
struct Trie{
    struct Node{
        int child[sz]{};
        bool e=0;
    };
    vector<Node>trie;
    Trie(){trie.emplace_back();}
    void insert(string &s){
        int idx=0,n=sz(s);
        for(int i=0;i<n;i++) {
            int nxt=s[i]-'a';
            if (trie[idx].child[nxt] == 0) {
                trie[idx].child[nxt] = sz(trie);
                trie.emplace_back();
            }
            idx = trie[idx].child[nxt];
        }
        trie[idx].e=1;
    }
    unordered_map<int,int>depth;
    int dep(int idx=0){
        int ret=0;
        for(int i=0;i<26;i++){
            if(!trie[idx].child[i])continue;
            ret=max(ret,dep(trie[idx].child[i]));
        }
        return depth[idx]=ret+1;
    }
    void query(int idx=0){
        if(trie[idx].e)ans.pb('P');
        vector<pair<int,int>>in;
        for(int i=0;i<26;i++){
            if(!trie[idx].child[i])continue;
            in.pb({depth[trie[idx].child[i]],i});
        }
        sort(all(in));
        for(auto it:in){
            ans.pb('a'+it.S);
            query(trie[idx].child[it.S]);
            ans.pb('-');
        }
    }
};
//-----------------------------------code-------------------------------------------//
void pewpew() {
    int n;cin>>n;
    Trie tr;
    for(int i=0;i<n;i++){
        string s;cin>>s;
        tr.insert(s);
    }
    tr.dep();
    tr.query();
    while(sz(ans) and ans.back()=='-')ans.pop_back();
    cout<<sz(ans)<<el;
    for(auto it:ans)cout<<it<<el;
}
//----------------------------------------------------------------------------------//
signed main()
{
    /* ☯︎☯︎☯︎ */    Bassmala    /* ☯︎☯︎☯︎ */
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt","w",stdout);
    int x_x = 1;
    //cin >> x_x;
    while (x_x--) {
        pewpew();
    }
    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