oj.uz

Submission #439454

# Submission time Handle Problem Language Result Execution time Memory
439454 2021-06-30T03:38:48 Z ldn694 Vlak (COCI20_vlak) C++17
70 / 70
 13 ms 10060 KB 
#include <bits/stdc++.h>
#define fu(i, a, b) for (int i = a; i <= b; i++)
#define fd(i, a, b) for (int i = a; i >= b; i--)
using namespace std;
const int N = 2e5 + 10;
int num[2];
int trie[N][27], sz = 0;
bool ticket[N][2];
void Insert(const string &a, int o)
{
    int pos = 0;
    for (char x : a)
    {
        int v = int(x) - 96;
        if (!trie[pos][v]) trie[pos][v] = ++sz;
        ticket[trie[pos][v]][o] = true;
        pos = trie[pos][v];
    }
}
bool win(int u, int o)
{
    bool passed = false;
    fu(i, 1, 26)
    {
        if (!trie[u][i]) continue;
        if (!ticket[trie[u][i]][o]) continue;
        passed |= !win(trie[u][i], 1 - o);
        if (passed) break;
    }
    return passed;
}
int main()
{
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    fu(i, 0, 1)
    {
        cin >> num[i];
        fu(j, 1, num[i])
        {
            string s;
            cin >> s;
            Insert(s, i);
        }
    }
    cout << (win(0, 0) ? "Nina" : "Emilija");
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9424 KB Output is correct
2 Correct 11 ms 8848 KB Output is correct
3 Correct 11 ms 8312 KB Output is correct
4 Correct 12 ms 9164 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9676 KB Output is correct
2 Correct 11 ms 10060 KB Output is correct
3 Correct 10 ms 9292 KB Output is correct
4 Correct 11 ms 9420 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9036 KB Output is correct
2 Correct 11 ms 8908 KB Output is correct
3 Correct 13 ms 9080 KB Output is correct
4 Correct 12 ms 9676 KB Output is correct