Submission #1217758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217758		leandroioilele	Vlak (COCI20_vlak)	C++20	70 / 70	16 ms	12120 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 pb push_back
#define INF 99999999999
#define NMAX 200005

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


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

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

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

int32_t main(){ faster 
    int n;
    cin>>n;
    string s;
    int x;
    inicio=new_node();
    v[inicio].tem[0]=1;
    v[inicio].tem[1]=1;
    dp[0]=-1;
    for(int i=0; i<n; i++){
        cin>>s;
        x=inicio;
        for(auto it:s){
            if(v[x].next.count(it)==0){
                v[x].next[it]=new_node();
            }
            x=v[x].next[it];
            dp[x]=-1;
            v[x].tem[0]=1;
        }
    }
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>s;
        x=inicio;
        for(auto it:s){
            if(v[x].next.count(it)==0){
                v[x].next[it]=new_node();
            }
            x=v[x].next[it];
            dp[x]=-1;
            v[x].tem[1]=1;
        }
    }
    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