Submission #953198

#TimeUsernameProblemLanguageResultExecution timeMemory
953198AverageAmogusEnjoyerVlak (COCI20_vlak)C++17
70 / 70
8 ms9952 KiB
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i,T j) { return i > j ? i = j, true : false; }
template<class T> bool cmax(T &i,T j) { return i < j ? i = j, true : false; }

constexpr int nax = 4e5;
int trie[nax][26];
bool who[nax][2];

bool dfs(int x,int turn) { // se vince il giocare 'turn' giocando da x
    for (int i=0;i<26;i++) {
        if (!trie[x][i]) { continue; }
        int y = trie[x][i];
        if (who[y][turn] && !dfs(y,turn^1)) { 
            return true;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int cnt = 1;
    while(n--) {
        string s;
        cin >> s;
        int u = 0;
        for (auto &c: s) {
            if (!trie[u][c-'a']) { trie[u][c-'a']=cnt++; }
            u = trie[u][c-'a'];
            who[u][0]=true;
        }
    }
    int m;
    cin >> m;
    while(m--) {
        string s;
        cin >> s;
        int u = 0;
        for (auto &c: s) {
            if (!trie[u][c-'a']) { trie[u][c-'a']=cnt++; }
            u = trie[u][c-'a'];
            who[u][1]=true;
        }
    }
    cout << (dfs(0,0) ? "Nina" : "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...