oj.uz

Submission #957233

# Submission time Handle Problem Language Result Execution time Memory
957233 2024-04-03T09:19:16 Z Surver Vlak (COCI20_vlak) C++17
70 / 70
 44 ms 15048 KB 
#include<bits/stdc++.h>
using namespace std;

const int K = 26;

struct Node{
    vector<int> next;
    bool output = false;
    Node(){
        next.resize(K, -1);
    }
};

class Trie{
    public:
    vector<Node> trie;
    Trie(){
        trie.resize(1);
    }

    void add(string &s){
        int v = 0;
        for (char ch : s){
            int c = ch - 'a';
            if (trie[v].next[c] == -1){
                trie[v].next[c] = trie.size();
                trie.emplace_back();
            }
            v = trie[v].next[c];
        }
        trie[v].output = true;
    }

    bool search(string &s){
        int v = 0;
        for (char ch : s){
            int c = ch - 'a';
            if (trie[v].next[c] == -1){
                return false;
            }
            v = trie[v].next[c];
        }
        return true;
    }
};

Trie t1, t2;
int calc2(string &s);

int calc1(string &s) {
    int mx = 0;
    for (int i = 0; i < K; i++) {
        s.push_back((char)('a' + i));
        if (t1.search(s)) {
            mx = max(mx, calc2(s));
        }
        s.pop_back();
    }
    return mx;
}

int calc2(string &s) {
    int mn = 1;
    for (int i = 0; i < K; i++) {
        s.push_back((char)('a' + i));
        if (t2.search(s)) {
            mn = min(mn, calc1(s));
        }
        s.pop_back();
    }
    return mn;
}

void solve(){
    int n;
    cin >> n;
    vector<string> v1(n);
    for (int i = 0; i < n; i++) {
        cin >> v1[i];
        t1.add(v1[i]);
    }
    int m;
    cin >> m;
    vector<string> v2(m);
    for (int i = 0; i < m; i++) {
        cin >> v2[i];
        t2.add(v2[i]);
    }
    string s = "";
    int x = calc1(s);
    cout << ((x == 0) ? "Emilija" : "Nina") << "\n";
}

int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    while(t--){
        solve();
    }
    return 0;
}

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 600 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 #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 460 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 25 ms 14604 KB Output is correct
2 Correct 25 ms 13772 KB Output is correct
3 Correct 25 ms 13004 KB Output is correct
4 Correct 29 ms 14280 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 14540 KB Output is correct
2 Correct 41 ms 15048 KB Output is correct
3 Correct 44 ms 14028 KB Output is correct
4 Correct 43 ms 14028 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 13772 KB Output is correct
2 Correct 30 ms 13512 KB Output is correct
3 Correct 27 ms 13768 KB Output is correct
4 Correct 33 ms 14796 KB Output is correct