oj.uz

Submission #401581

# Submission time Handle Problem Language Result Execution time Memory
401581 2021-05-10T13:49:51 Z jenkinsser Vlak (COCI20_vlak) C++17
70 / 70
 30 ms 33788 KB 
#include <bits/stdc++.h>
#define FOR(ii,aa,bb) for(int ii=aa;ii<bb;ii++)
#define for0(ii,bb) FOR(ii,0,bb)
#define for1(ii,bb) FOR(ii,1,bb+1)
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define st first
#define nd second
#define pii pair<int,int>
#define piii pair<int,pii>
#define piiii pair<pii,pii>
#define pdi pair<double,int>
#define vi vector<int>
#define sp " "
#define nl "\n"
#define all(x) x.begin(),x.end()
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define int ll

using namespace std;

const int N = 2e5+5;
const int INF = 1e9+5;
const int mod = 1e9+7;

struct node{
    int kenarlar[26];
};

node trie1[N],trie2[N];
int n,m,nodesayisi1=1,nodesayisi2=1;
string s[N],t[N];

void ekle1(string str){
    int cur_node=1;
    for(int i=0;i<(int)str.size();i++){
        int c=str[i]-'a';
        if(trie1[cur_node].kenarlar[c]==0){
            nodesayisi1++;
            trie1[cur_node].kenarlar[c]=nodesayisi1;
        }
        cur_node=trie1[cur_node].kenarlar[c];
    }
}

void ekle2(string str){
    int cur_node=1;
    for(int i=0;i<(int)str.size();i++){
        int c=str[i]-'a';
        if(trie2[cur_node].kenarlar[c]==0){
            nodesayisi2++;
            trie2[cur_node].kenarlar[c]=nodesayisi2;
        }
        cur_node=trie2[cur_node].kenarlar[c];
    }
}

int bul1(string str){
    int cur_node=1;
    for(int i=0;i<(int)str.size();i++){
        int c=str[i]-'a';
        if(trie1[cur_node].kenarlar[c]==0)
            return 0;
        cur_node=trie1[cur_node].kenarlar[c];
    }
    for(int i=0;i<26;i++)
        if(trie1[cur_node].kenarlar[i])
            return cur_node;
    return 0;
}

int bul2(string str){
    int cur_node=1;
    for(int i=0;i<(int)str.size();i++){
        int c=str[i]-'a';
        if(trie2[cur_node].kenarlar[c]==0)
            return 0;
        cur_node=trie2[cur_node].kenarlar[c];
    }
    for(int i=0;i<26;i++)
        if(trie2[cur_node].kenarlar[i])
            return cur_node;
    return 0;
}

bool solve(string str,bool flag){
    // cout << str << sp << flag << nl;
    if(flag){
        int a=bul1(str);
        if(!a)
            return false;
        bool res=false;
        for(int i=0;i<26;i++){
            if(trie1[a].kenarlar[i]){
                res|=solve(str+char(i+'a'),!flag);
            }
        }
        return res;
    }
    else{
        int a=bul2(str);
        if(!a){
            // cout << str << nl;
            return true;
        }
        bool res=true;
        for(int i=0;i<26;i++){
            if(trie2[a].kenarlar[i]){
                // cout << str << sp << char(i+'a') << nl;
                res&=solve(str+char(i+'a'),!flag);
            }
        }
        return res;
    }
}

signed main(){
    fastio()
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> s[i];
        ekle1(s[i]);
    }
    cin >> m;
    for(int i=1;i<=m;i++){
        cin >> t[i];
        ekle2(t[i]);
    }
    bool res=false;
    for(int i=0;i<26;i++){
        if(trie1[1].kenarlar[i]){
            string str;
            str+=char('a'+i);
            res|=solve(str,0);
            // cout << str << sp << solve(str,0) << nl;
        }
    }
    if(res)
        cout << "Nina";
    else
        cout << "Emilija";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 13004 KB Output is correct
2 Correct 9 ms 13132 KB Output is correct
3 Correct 9 ms 13020 KB Output is correct
4 Correct 9 ms 12996 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 13132 KB Output is correct
2 Correct 9 ms 13100 KB Output is correct
3 Correct 9 ms 13004 KB Output is correct
4 Correct 8 ms 13104 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 13004 KB Output is correct
2 Correct 9 ms 12988 KB Output is correct
3 Correct 8 ms 13004 KB Output is correct
4 Correct 9 ms 13004 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12976 KB Output is correct
2 Correct 9 ms 13004 KB Output is correct
3 Correct 9 ms 13104 KB Output is correct
4 Correct 9 ms 13004 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 32604 KB Output is correct
2 Correct 27 ms 31320 KB Output is correct
3 Correct 27 ms 30364 KB Output is correct
4 Correct 29 ms 32076 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 32836 KB Output is correct
2 Correct 30 ms 33788 KB Output is correct
3 Correct 29 ms 32060 KB Output is correct
4 Correct 28 ms 32432 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 31844 KB Output is correct
2 Correct 26 ms 31308 KB Output is correct
3 Correct 27 ms 31828 KB Output is correct
4 Correct 29 ms 33044 KB Output is correct