oj.uz

Submission #692238

# Submission time Handle Problem Language Result Execution time Memory
692238 2023-02-01T08:43:01 Z tamthegod Vlak (COCI20_vlak) C++17
10 / 70
 57 ms 96272 KB 
// 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[30];
    };
    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<27; w++)
            {
                if(tree[id].child[w] != -1 && tree[tree[id].child[w]].type != 1)
                {
                    ok |= get(tree[id].child[w], turn ^ 1);
                }
            }
            return ok;
        }
        else
        {
            bool ok = true;
            for(int w=0; w<27; w++)
            {
                if(tree[id].child[w] != -1 && tree[tree[id].child[w]].type != 2)
                {
                    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("CONC.inp", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Solve();
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 63572 KB Output is correct
2 Correct 32 ms 63496 KB Output is correct
3 Incorrect 32 ms 63480 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 63580 KB Output is correct
2 Correct 29 ms 63564 KB Output is correct
3 Incorrect 29 ms 63576 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 63280 KB Output is correct
2 Incorrect 29 ms 63572 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 63312 KB Output is correct
2 Correct 30 ms 63576 KB Output is correct
3 Correct 33 ms 63476 KB Output is correct
4 Correct 30 ms 63352 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 96212 KB Output is correct
2 Incorrect 57 ms 96272 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 96096 KB Output is correct
2 Incorrect 53 ms 96112 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 96184 KB Output is correct
2 Incorrect 54 ms 96196 KB Output isn't correct
3 Halted 0 ms 0 KB -