Submission #1297377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297377		alyyy	Type Printer (IOI08_printer)	C++20	100 / 100	122 ms	101044 KiB

printer

// #define OJ
// #define TEST


#include <bits/stdc++.h>
using namespace std;
#ifdef OJ
    #pragma GCC target("avx2")
    #pragma GCC optimize("O3")
    #pragma GCC optimize("unroll-loops")
#endif
#ifndef ALY
#define ALY
    static int __star = []{
        ios_base::sync_with_stdio(0);
        cin.tie(NULL),cout.tie(NULL);
        return 0;
    }();
    using ll = long long;
    using ull = unsigned long long;
    using uint = unsigned int;
    using u8 = uint8_t;
    using u16 = uint16_t;
    using u32 = uint32_t;
    using u64 = uint64_t;
    using in8 = uint8_t;
    using in16 = uint16_t;
    using in32 = uint32_t;
    using in64 = uint64_t;
    using db = long double;
    using str = string;
    using pi = pair<int,int>;
    using pl = pair<ll,ll>;
    #define mp make_pair
    #define f first
    #define s second
    #define vcA template<class A
    vcA> using V = vector<A>;
    vcA> using MAT = V<V<A>>;
    using vi = V<int>;
    using vb = V<bool>;
    using vl = V<ll>;
    using vd = V<db>;
    using vs = V<str>;
    using vpi = V<pi>;
    using vpl = V<pl>;
    using mat = V<vi>;
    using matl = V<vl>;
    #define sz(x) int((x).size())
    #define bg(x) begin(x)
    #define rbg(x) rbegin(x)
    #define ed(x) end(x)
    #define all(x) begin(x), end(x)
    #define pfr(x, a) begin(x), begin(x) + a
    #define rall(x) x.rbegin(), x.rend()
    #define srt(x) sort(all(x))
    #define nth(x, a) nth_element(pfr(x, a), ed(x))
    #define npp(x) next_permutation(all(x))
    #define shl(x, a) ((x) << (a))
    #define shr(x, a) ((x) >> (a))
    #define pb push_back
    #define pf push_front
    #define eb emplace_back
    #define em empty()
    #define ft front()
    #define bk back()
    #define ppb pop_back()
    #define ppf pop_front()
    #define pp pop()
    #define tp top()
    #define lb lower_bound
    #define ub upper_bound
    #define FOR(i, a, b) for(int i = (a); i < (b); ++i)
    #define F0R(i, a) FOR(i, 0, a)
    #define ROF(i, a, b) for(int i = (b) - 1; i >= (a); --i)
    #define R0F(i, a) ROF(i, 0, a)
    #define xtime(a) F0R(_, a)
    #define each(a, x) for(auto& a : x)
    static constexpr int MOD = 1'000'000'007;
    static constexpr int MD2 = 1'000'000'009;
    static constexpr int ALT = 998'244'353;
    static constexpr u64 B1 = 911'382'323;
    static constexpr u64 B2 = 972'663'749;
    static constexpr ll LMX = 1e18;
    static constexpr int XDIR[4] {1, 0, -1, 0}, YDIR[4] {0, 1, 0, -1};
    template<class P> using pqpl = priority_queue<P, vector<P>, greater<P>>;
    template<class P> using pqpg = priority_queue<P, vector<P>, less<P>>;
    constexpr int pct(int x) { return __builtin_popcount(x); }
    constexpr int ctz(int x) { return __builtin_ctz(x); }
    constexpr int clz(int x) { return __builtin_clz(x); }
    constexpr int pctll(ll x) { return __builtin_popcountll(x); }
    constexpr int ctzll(ll x) { return __builtin_ctzll(x); }
    constexpr int clzll(ll x) { return __builtin_clzll(x); }
    ll ceill(ll a, ll b) { return (a + b - 1) / b; }
    vcA> void printvec(V<A>&a) { each(v,a) { cout << v << ' '; } cout << '\n'; }
    // binstr
    template<typename C>
    void meow(C num) { for(int bits = sizeof(num) * 8; bits--; num >>= 1) cout << !!(num & 1); cout << '\n'; }
    // pos of msb, msb(0) = -1, msb(2) = 1, msb(1) = 0, etc.
    template<typename C>
    int woof(C n) {
        if(!n) return -1;
        switch(sizeof(C)) {
            case 1: return 7 - clz(static_cast<uint>(n) << 24);
            case 2: return 15 - clz(static_cast<uint>(n) << 16);
            case 4: return 31 - clz(static_cast<uint>(n));
            case 8: return 63 - clzll(static_cast<ull>(n));
        }
        return -1;
    }
    // for coordinate comp
    template<typename T>
    int v2i(V<T>& A, T val) { return int(lower_bound(all(A), val) - bg(A)); }
#endif


struct node {
    int depth = 0, word = 0;
    node* nxt[26]{nullptr};
};


struct trie {
    node* root;
    trie(vs& A) : root(new node) {
        each(i, A) ins(i);
        pull(root, 0);
    };

    void ins(str& s) {
        node* cur = root;
        each(c, s) {
            auto& nxt = cur->nxt[c - 'a'];
            if(!nxt) nxt = new node;
            cur = nxt;
        }
        cur->word = 1;
    }

    int pull(node* cur, int d) {
        int ret = d;
        F0R(i, 26) if(cur->nxt[i])
            ret = max(ret, pull(cur->nxt[i], d + 1));
        return cur->depth = ret;
    }

    void dfs(node* cur, str& s) {
        if(cur->word) s.pb('P');
        F0R(i, 26) if(cur->nxt[i]) {
            s.pb(char('a' + i));
            dfs(cur->nxt[i], s);
            s.pb('-');
        }
    }

    void solve(node* cur, str& s) {
        if(cur->word) s.pb('P');
        int nxt = -1;
        F0R(i, 26) if(cur->nxt[i]) {
            if(cur->nxt[i]->depth == cur->depth && nxt == -1) {
                nxt = i;
                continue;
            }
            s.pb(char('a' + i));
            dfs(cur->nxt[i], s);
            s.pb('-');
        }
        if(nxt == -1) return;
        s.pb(char('a' + nxt));
        solve(cur->nxt[nxt], s);
    }

    void solve() {
        str s;
        solve(root, s);
        cout << sz(s) << '\n';
        each(c, s) cout << c << '\n';
    }
};


int main() {
#ifdef TEST
#else
    int n; cin >> n;
    vs A(n); each(i, A) cin >> i;
    trie T(A);
    T.solve();
#endif
    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