제출 #1341495

#제출 시각아이디문제언어결과실행 시간메모리
1341495mwenVlak (COCI20_vlak)C++20
70 / 70
18 ms19812 KiB
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)

constexpr int MAX_SIZE = 300000;

struct Trie {
    int cnt;
    vector<map<char, int>> con;
    vector<int> type;
    Trie(): cnt(1), con(MAX_SIZE), type(MAX_SIZE) {}
    void add(const string& s, int player) {
        int curr = 0;
        for(char c : s) {
            if(con[curr].count(c) == 0)
                con[curr][c] = cnt++;
            curr = con[curr][c];
            type[curr] |= (1<<player);
        }
    }
    bool wins(int curr, int player) {
        bool win = false;
        for(auto [_, next] : con[curr]) {
            if(type[next]&(1<<player))
                if(!wins(next, 1-player))
                    win = true;
        }
        return win;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    Trie trie;
    for(int player = 0; player <= 1; player++) {
        int n;
        cin >> n;
        for(int i = 0; i < n; i++) {
            string s;
            cin >> s;
            trie.add(s, player);
        }
    }
    if(trie.wins(0, 0))
        cout << "Nina\n";
    else
        cout << "Emilija\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...