제출 #1297337

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1297337		alyyy	Vlak (COCI20_vlak)	C++20	70 / 70	17 ms	20736 KiB

Main

// #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


/*
    terminal nodes are nodes where:
    1. no children
    2. node is only a prefix of some word belonging to p1
    3. prefix belongs to p2 only

    case 1: losing position, as p1 cannot move from here
    case 2: iff not case 1, then no matter what we choose, p2 cannot move, :. winning position for p1
    case 3: iff not case 1, then p1 cannot move, :. losing

    game is only played on common prefixes
    common prefix leaf node is either winning or losing
    > winning if there exists 1 child that has mask & 1
    > losing if all children have mask & 2
*/


struct node {
    u8 mask = 0, ewin = 0, nwin = 0;
    node* nxt[26]{nullptr};
};


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

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

    void pull(node* cur) {
        // n wins when there is >= 1 child with !ewin
        int cmask = cur->mask;
        F0R(i, 26) if(cur->nxt[i]) {
            pull(cur->nxt[i]);
            int nmask = cur->nxt[i]->mask;
            cur->nwin |= ((cmask & 1) && !cur->nxt[i]->ewin && (nmask & 1));
            cur->ewin |= ((cmask & 2) && !cur->nxt[i]->nwin && (nmask & 2));
        }
    }
};


int main() {
#ifdef TEST
#else
    int n; cin >> n;
    vs A(n); each(i, A) cin >> i;
    int m; cin >> m;
    vs B(m); each(i, B) cin >> i;
    trie T(A, B);
    cout << (T.root->nwin ? "Nina\n" : "Emilija\n");
#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