Submission #692398

#	Time	Username	Problem	Language	Result	Execution time	Memory
692398		tamthegod	Vlak (COCI20_vlak)	C++17	70 / 70	73 ms	101660 KiB

Main

// Make the best become better
// No room for laziness
#include<bits/stdc++.h>

#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int n, m;
string s[maxN], t[maxN];
void ReadInput()
{
    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> s[i];
    cin >> m;
    for(int i=1; i<=m; i++)
        cin >> t[i];
}
struct Trie
{
    struct TNode
    {
        int id;
        int type;
        int child[35];
    };
    vector<TNode> tree;
    void new_node()
    {
        TNode tmp;
        tmp.id = tree.size();
        tmp.type = 0;
        for(int i=0; i<30; i++)
            tmp.child[i] = -1;
        tree.pb(tmp);
    }
    void add(string s, int type)
    {
        int id = 0;
        for(char c : s)
        {
            int w = c - 'a';
            if(tree[id].child[w] == -1)
            {
                new_node();
                tree[id].child[w] = tree.size() - 1;
            }
            id = tree[id].child[w];
            tree[id].type |= type;
        }
        tree[id].type |= type;
    }
    bool get(int id, int turn)
    {
        if(!(turn & 1))
        {
            bool ok = false;
            for(int w=0; w<30; w++)
            {
                if(tree[id].child[w] != -1 && tree[tree[id].child[w]].type != 2)
                {
                    ok |= get(tree[id].child[w], turn ^ 1);
                }
            }
            return ok;
        }
        else
        {
            bool ok = true;
            for(int w=0; w<30; w++)
            {
                if(tree[id].child[w] != -1 && tree[tree[id].child[w]].type != 1)
                {
                    ok &= get(tree[id].child[w], turn ^ 1);
                }
            }
            return ok;
        }
    }
};
void Solve()
{
    Trie trie;
    trie.new_node();
    for(int i=1; i<=n; i++)
        trie.add(s[i], 1);
    for(int i=1; i<=m; i++)
        trie.add(t[i], 2);
    cout << (trie.get(0, 0) ? "Nina" : "Emilija");
}
int32_t main()
{
   // freopen("x.inp", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Solve();
}

• 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