oj.uz

Submission #377396

# Submission time Handle Problem Language Result Execution time Memory
377396 2021-03-14T06:54:08 Z NONAME Vlak (COCI20_vlak) C++17
70 / 70
 256 ms 106220 KB 
#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int n, m, total;

struct st {
    int nxt[26];
    bool have[2];

    st() {
        for (int i = 0; i < 26; ++i) {
            nxt[i] = -1;
        }
        have[0] = have[1] = false;
    }
} trie[(int)(1e6)];

void add(string& s, int tp) {
    int v = 0;
    for (int i = 0; i < (int)(s.size()); ++i) {
        int j = s[i] - 'a';
        if (trie[v].nxt[j] == -1) {
            trie[v].nxt[j] = ++total;
        }
        trie[v].have[tp] = true;
        v = trie[v].nxt[j];
    }
    trie[v].have[tp] = true;
}

bool solve(int v, int tp) {
    for (int i = 0; i < 26; ++i) {
        if ((trie[v].nxt[i] == -1) || !trie[trie[v].nxt[i]].have[tp]) {
            continue;
        }

        bool f = solve(trie[v].nxt[i], tp ^ 1);

        if (!f) {
            // cerr << v << " " << 1 << "\n";
            return true;
        }
    }
    // cerr << v << " " << 0 << "\n";
    return false;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        add(s, 0);
    }

    cin >> m;
    for (int i = 0; i < m; ++i) {
        string s;
        cin >> s;
        add(s, 1);
    }

    cout << (solve(0, 0) ? "Nina" : "Emilija") << "\n";

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 105964 KB Output is correct
2 Correct 69 ms 105964 KB Output is correct
3 Correct 256 ms 106036 KB Output is correct
4 Correct 75 ms 105964 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 105964 KB Output is correct
2 Correct 75 ms 105964 KB Output is correct
3 Correct 69 ms 105964 KB Output is correct
4 Correct 74 ms 105964 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 105964 KB Output is correct
2 Correct 68 ms 105964 KB Output is correct
3 Correct 71 ms 105964 KB Output is correct
4 Correct 69 ms 105964 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 105964 KB Output is correct
2 Correct 77 ms 106092 KB Output is correct
3 Correct 81 ms 105964 KB Output is correct
4 Correct 69 ms 105964 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 105964 KB Output is correct
2 Correct 73 ms 106220 KB Output is correct
3 Correct 73 ms 106220 KB Output is correct
4 Correct 73 ms 106116 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 105964 KB Output is correct
2 Correct 72 ms 105964 KB Output is correct
3 Correct 72 ms 106092 KB Output is correct
4 Correct 72 ms 106092 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 105964 KB Output is correct
2 Correct 72 ms 105964 KB Output is correct
3 Correct 73 ms 106092 KB Output is correct
4 Correct 74 ms 105964 KB Output is correct