oj.uz

Submission #1003346

# Submission time Handle Problem Language Result Execution time Memory
1003346 2024-06-20T09:05:29 Z nmts Type Printer (IOI08_printer) C++17
100 / 100
 137 ms 138948 KB 
#include <bits/stdc++.h>

#define file(name) freopen(name".inp" , " r " , stdin);freopen(name".out" , " w " , stdout)
#define faster    ios_base :: sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;
#define pii pair < int , int >
#define pdd pair < double , double >
#define fi first
#define se second
#define mii map< int , int>
#define mdd map< double , double >
#define qi queue < int >
#define dqi deque< int >
#define pf(x) push_front(x)
#define popf pop_front()
#define reset(a,val) memset(a ,val , sizeof(a) )
#define count_bit(i) __builtin_popcountll(i) 
#define mask(i) ((1LL << (i)))  
#define status(x, i) (((x) >> (i)) & 1)  
#define set_on(x, i) ((x) | mask(i)) 
#define set_off(x, i) ((x) & ~mask(i))
#define endl '\n'    
#define int long long
const int maxn = 1e6 + 6;
const int mod= 1e9 + 7;
const int INF= 1e9;
const int LOG = 20 ;


template <class T> inline T sqr(T x) { return x * x; };

template <class T> inline int Power(T x, int y) 

{ if (!y) return 1; if (y & 1) return sqr(Power(x, y / 2)) % mod * x % mod; return sqr(Power(x, y / 2)) % mod; }

template<class T> bool minimize(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool maximize(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

inline int gcd(int x, int y) 
{ return y ? gcd(y , x % y) : x;}

inline int lcm(int x, int y) { return x * y / gcd(x, y); }

using namespace std;

vector<char> ans;
int idx = 0;
int n;
struct Trie{

    struct Node{

        Node* child[26];
        int exits ;
        int sz;
        Node()
            {
                for (int i=0 ; i<26 ; ++i) child[i] = NULL;
                exits = 0;
                sz = 1;
            }
    };

    Node* root;

    Trie()
        {
            root = new Node;
        };

    void add(string s)
        {
            Node* p = root;
            for (int i=0 ; i < (int)s.size() ; ++i)
                {
                    int c = s[i] - 'a';
                    if (p->child[c] == NULL) { p->child[c] = new Node ;  }
                    p=p->child[c];
                }
            p->exits++;
        }

    void dfs(Node* p)
        {
            p->sz = 1;
            for (int i=0 ; i<26 ; ++i)
                if (p->child[i] != NULL)
                    {
                        dfs(p->child[i]);
                        p->sz = max(p->sz , p->child[i]->sz + 1);
                    }
        }
    

    void get_ans(Node* p)
        {
            if (p->exits != 0)
                {
                    ans.push_back('P');
                    idx++;
                }

            vector<pair<int , pair<Node* , int>>> path;

            for (int i=0 ; i<26 ; ++i)
                if (p->child[i] != NULL)
                    {
                        path.push_back({p->child[i]->sz , {p->child[i] , i}});
                    }
            
            sort(path.begin() , path.end());

            for (auto it : path)
                {
                    ans.push_back(it.se.se + 'a');
                    get_ans(it.se.fi);
                    if (idx < n) ans.push_back(45);
                }

        }

    void prepare()
        {
            Node*p = root;
            dfs(p);
            get_ans(p);
        }

};


Trie tr;
string a[maxn];


void solve()
{

    cin >> n ;

    for (int i=1 ; i<=n; ++i)
        {
            cin >> a[i];
            tr.add(a[i]);
        }

    tr.prepare();
    

    cout << ans.size() << endl;

    // reverse(ans.begin() , ans.end());
    for (auto x : ans) cout << x << endl;

}


int32_t main()
{
    faster;
    #ifdef ONLINE_JUDGE
    file("txt");
    #else
    // online submission
    #endif
    // int t ; cin >> t ; while (t--)
    solve();
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31580 KB Output is correct
2 Correct 13 ms 31580 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31576 KB Output is correct
2 Correct 16 ms 31580 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31580 KB Output is correct
2 Correct 12 ms 31580 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 31576 KB Output is correct
2 Correct 14 ms 31772 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31836 KB Output is correct
2 Correct 13 ms 32604 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 33372 KB Output is correct
2 Correct 16 ms 33880 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37724 KB Output is correct
2 Correct 26 ms 44892 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47104 KB Output is correct
2 Correct 20 ms 35108 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 70816 KB Output is correct
2 Correct 115 ms 121796 KB Output is correct
3 Correct 67 ms 78540 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 61900 KB Output is correct
2 Correct 137 ms 138948 KB Output is correct
3 Correct 76 ms 84944 KB Output is correct
4 Correct 116 ms 133060 KB Output is correct