oj.uz

Submission #692398

# Submission time Handle Problem Language Result Execution time Memory
692398 2023-02-01T12:00:03 Z tamthegod Vlak (COCI20_vlak) C++17
70 / 70
 73 ms 101660 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[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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 63632 KB Output is correct
2 Correct 30 ms 63656 KB Output is correct
3 Correct 30 ms 63652 KB Output is correct
4 Correct 29 ms 63624 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 63656 KB Output is correct
2 Correct 31 ms 63648 KB Output is correct
3 Correct 30 ms 63676 KB Output is correct
4 Correct 33 ms 63668 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 63320 KB Output is correct
2 Correct 30 ms 63656 KB Output is correct
3 Correct 31 ms 63312 KB Output is correct
4 Correct 29 ms 63636 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 63316 KB Output is correct
2 Correct 31 ms 63636 KB Output is correct
3 Correct 36 ms 63592 KB Output is correct
4 Correct 35 ms 63292 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 101556 KB Output is correct
2 Correct 65 ms 101548 KB Output is correct
3 Correct 60 ms 101660 KB Output is correct
4 Correct 63 ms 101556 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 101444 KB Output is correct
2 Correct 68 ms 101416 KB Output is correct
3 Correct 58 ms 101420 KB Output is correct
4 Correct 65 ms 101492 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 101476 KB Output is correct
2 Correct 73 ms 101480 KB Output is correct
3 Correct 65 ms 101568 KB Output is correct
4 Correct 66 ms 101552 KB Output is correct