oj.uz

Submission #867140

# Submission time Handle Problem Language Result Execution time Memory
867140 2023-10-27T18:06:08 Z Samrev Vlak (COCI20_vlak) C++14
70 / 70
 9 ms 17100 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 712 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 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 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15560 KB Output is correct
2 Correct 9 ms 15564 KB Output is correct
3 Correct 9 ms 17100 KB Output is correct
4 Correct 9 ms 16844 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16328 KB Output is correct
2 Correct 8 ms 14796 KB Output is correct
3 Correct 7 ms 15308 KB Output is correct
4 Correct 7 ms 16580 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16076 KB Output is correct
2 Correct 8 ms 16076 KB Output is correct
3 Correct 8 ms 16816 KB Output is correct
4 Correct 8 ms 16588 KB Output is correct