oj.uz

Submission #930877

# Submission time Handle Problem Language Result Execution time Memory
930877 2024-02-20T14:55:07 Z woofes Vlak (COCI20_vlak) C++17
70 / 70
 12 ms 16848 KB 
// #pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int cnt_s = 26;

struct node {
    int val;
    int lnk[cnt_s];
    bool st1;
    bool st2;
    node() {
        st1 = true;
        st2 = true;
        for (int i = 0; i < cnt_s; i++) {
            lnk[i] = -1;
        }
    }
    node(int v, bool s) {
        val = v;
        st1 = false;
        st2 = false;
        for (int i = 0; i < cnt_s; i++) {
            lnk[i] = -1;
        }
    }
};

vector<node> trie(1);

void add(string& s, int pd) {
    int v = 0;
    for (int i = s.size() - 1; i >= 0; i--) {
        int ind = s[s.size() - 1 - i] - 'a';
        int u = trie[v].lnk[ind];
        if (u == -1) {
            u = trie.size();
            trie[v].lnk[ind] = u;

            node nd(ind, false);
            trie.push_back(nd);
        }
        v = u;
        if (pd) {
            trie[v].st1 = true;
        } else {
            trie[v].st2 = true;
        }
    }
}

bool find_d(int v, int deep) {
    if (v == -1) {
        return 1;
    }
    if (deep % 2 == 0) {
        if (!trie[v].st1) {
            return 1;
        }
    } else {
        if (!trie[v].st2) {
            return 1;
        }
    }

    for (int i : trie[v].lnk) {
        if (!find_d(i, deep + 1)) {
            return 1;
        }
    }
    return 0;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    // freopen("input.txt", "r", stdin);

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

    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        add(s, 1);
    }
    int res = find_d(0, 0);
    if (!res) {
        cout << "Emilija";
    } else {
        cout << "Nina";
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15408 KB Output is correct
2 Correct 10 ms 16072 KB Output is correct
3 Correct 9 ms 16568 KB Output is correct
4 Correct 10 ms 15820 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16844 KB Output is correct
2 Correct 10 ms 15556 KB Output is correct
3 Correct 12 ms 16848 KB Output is correct
4 Correct 11 ms 16332 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15816 KB Output is correct
2 Correct 9 ms 15936 KB Output is correct
3 Correct 9 ms 15304 KB Output is correct
4 Correct 9 ms 16068 KB Output is correct