Submission #957233

#	Time	Username	Problem	Language	Result	Execution time	Memory
957233		Surver	Vlak (COCI20_vlak)	C++17	70 / 70	44 ms	15048 KiB

Main

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10