Submission #1215323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215323		leandroioilele	Vlak (COCI20_vlak)	C++20	70 / 70	26 ms	20124 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define faster ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define NMAX 200005
#define pb push_back

struct node{
    bool ans[2];
    unordered_map<char,int>next;
    node(){
        ans[1]=ans[0]=0;
        next.clear();
    }
};


vector<node>v;
int dp[NMAX];

int inicio;

int new_node(){
    v.pb(node());
    return v.size()-1;
}

bool solve(int x, int id){
    if(id==0 && v[x].ans[id]==0)return false;
    if(id==1 && v[x].ans[id]==0)return true;
    if(dp[x]!=-2)return dp[x];
    if(id==0){
        dp[x]=false;
        for(auto it:v[x].next){
            if(solve(it.second, 1)==true){
                dp[x]=true;
            }
        }
    }
    else{
        dp[x]=true;
        for(auto it:v[x].next){
            if(solve(it.second, 0)==false){
                dp[x]=false;
                break;
            }
        }
    }

    return dp[x];
}


int32_t main(){ faster 
    int n;
    cin>>n;
    string s;
    inicio=new_node();
    while(n--){
        cin>>s;
        int x=inicio;
        v[x].ans[0]=v[x].ans[1]=1;
        for(auto it:s){
            if(v[x].next.count(it)==0){
                v[x].next[it]=new_node();
            }
            x=v[x].next[it];
            v[x].ans[0]=1;
        }
    }
    cin>>n;
    while(n--){
        cin>>s;
        int x=inicio;
        v[x].ans[0]=v[x].ans[1]=1;
        for(auto it:s){
            if(v[x].next.count(it)==0){
                v[x].next[it]=new_node();
            }
            x=v[x].next[it];
            v[x].ans[1]=1;
        }
    }
    for(int i=0; i<NMAX; i++){
        dp[i]=-2;
    }
    cout<<(solve(0,0)==1?"Nina":"Emilija")<<"\n";

}

• 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