Submission #867140

#	Time	Username	Problem	Language	Result	Execution time	Memory
867140		Samrev	Vlak (COCI20_vlak)	C++14	70 / 70	9 ms	17100 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define LSOne(x) (x&(-x))
typedef long long int ll;
typedef long double ld;
ll t = 1;
const ll M = 1e9 + 7;
ll mod_add(ll a, ll b){
    return ((a%M) + (b %M))%M;
}
ll mod_minus(ll a , ll b){
    return ((a%M) - (b %M) + M)%M;
}
ll mod_mul(ll a, ll b){
    return ((a%M)*(b%M))%M;
}
ll power(ll a, ll b){
    ll ans = 1;
    while(b > 0){
        if(b % 2 == 1){
            ans = mod_mul(ans , a);
        }
        a = mod_mul(a , a);
        b = b/2;
    }
    return ans;
}
ll mod_inverse(ll a){
    return power(a, M-2);
}

ll mod_divide(ll a, ll b){
    return mod_mul(a , mod_inverse(b));
}



const ll MAX = 1e18;
 
ll lcm(ll a , ll b){
    return (a*b)/__gcd(a,b);
}
const ll N = 1e5 + 10;

int n , m ;
vector<string> a, b;
const int K = 26;
struct Vertex{
    int next[K];
    bool p1 = false;
    bool p2 = false;
    bool win = false;
    Vertex(){
        fill(begin(next), end(next), -1);
    }
};
vector<Vertex> trie(1);
void add_string(string &s , int p){
    int v = 0;
    if(p == 1){
        trie[v].p1 = true;
    }
    else{
        trie[v].p2 = true;
    }
    for(auto 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];
        if(p == 1){
            trie[v].p1 = true;
        }
        else{
            trie[v].p2 = true;
        }
    }
}
void cal(int v, int turn){
    if(turn){
        if(!trie[v].p1) return;
    }
    else {
        if(!trie[v].p2) return;
    }
    for(int i = 0;i<K;i++){
        if(trie[v].next[i] == -1) continue;
        cal(trie[v].next[i], 1- turn);    
        if(!trie[trie[v].next[i]].win){
            trie[v].win = true;
            break;
        }
    }
}
void solve(){
    cin>>n;
    a.resize(n);
    for(int i = 0 ; i<n;i++){
        cin>>a[i];
        add_string(a[i],1);
    }
    cin>>m;
    b.resize(m);
    for(int i = 0;i<m;i++){
        cin>>b[i];
        add_string(b[i],2);
    }
    cal(0,1);
    if(trie[0].win){
        cout<<"Nina\n";
    }
    else{
        cout<<"Emilija\n";
    }





    

}
int main(){
 
    ios::sync_with_stdio(0); cin.tie(0);
    // freopen("input.txt" , "r" , stdin);
    // freopen("output.txt" , "w", stdout);
    // cin>>t;
    while(t--){
        solve();
    }
}

• 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