Submission #1206558

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206558		leandropina	Vlak (COCI20_vlak)	C++20	70 / 70	17 ms	14192 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define NMAX 100005
#define int long long
#define pii pair<int,int>
#define tt tuple<int,int,int>
#define INF 1e18
#define MOD 1000000007
#define faster ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ost tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define LSB(x) ((x)&-(x))
#define count_bits(x) __builtin_popcount(x)
#define leading_zeros(x) __builtin_clz(x)
#define trailing_zeros(x) __builtin_ctz(x)
#define all(x) begin(x),end(x)
#define pb push_back
#define eps 1e-9

struct node{
    int nivel;
    int cnt[2];
    map<char,int>next;
    node(){
        nivel = 0;
        cnt[0] = cnt[1] = 0;
        next.clear();
    }
};
vector<node>tri={node()};

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

void insere(string &s, int tipo){
    int x = 0;
    int nivel = 0;
    tri[x].cnt[tipo]++;
    for(auto ch:s){
        if(tri[x].next.count(ch)==0){
            tri[x].next[ch] = new_node();
        }
        x = tri[x].next[ch];
        tri[x].nivel = ++nivel;
        tri[x].cnt[tipo]++;
    }
}

int dp[200005];
int solve(int x){
    if(dp[x]!=-1) return dp[x];
    int turno = tri[x].nivel & 1;
    dp[x] = 0;
    if(tri[x].cnt[turno]==0) return 0;
    for(auto [ch,next_id]:tri[x].next){
        if(solve(next_id)==0){
            dp[x] = 1;
        }
    }
    return dp[x];
}

int32_t main(){ faster
    int n; cin >> n;
    for(int i=0;i<n;i++){
        string s; cin >> s;
        insere(s,0);
    }
    int m; cin >> m;
    for(int i=0;i<m;i++){
        string s; cin >> s;
        insere(s,1);
    }
    memset(dp,-1,sizeof dp);
    int ans = solve(0);
    if(ans==1) cout << "Nina\n";
    else cout << "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