Submission #1003200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003200		amin_2008	Vlak (COCI20_vlak)	C++17	70 / 70	23 ms	21340 KiB

Main

#include "bits/stdc++.h"

using namespace std;

#define int long long 

const int sz = 2e5 + 5;
const int inf = 1e18;

int trie[sz][26];
int cnt[sz];
int dp[sz];
int stop[sz], endd[sz];
int nxt = 0;

struct Trie
{
    void add(string s, int id) 
    {
        int root = 0;
        for(char c : s) 
        {
            int child = c - 'a';
            cnt[root]++;
            if (!trie[root][child]) trie[root][child] = ++nxt;
            root = trie[root][child];
        }
        if (id == 1) stop[root] = 1;
        else endd[root] = 1;
    }
    void play(int root, int depth) 
    {
        for(int i = 0; i < 26; i++) if (trie[root][i]) play(trie[root][i], depth + 1);
        if (depth % 2) 
        {
            if (!cnt[root]) 
            {
                dp[root] = (endd[root] == 1) ? 2 : 1;
                return;
            }
            for(int i = 0; i < 26; i++) if (trie[root][i]) if (dp[trie[root][i]] == 1) dp[root] = 1;
            if (!dp[root]) dp[root] = 2;
        }
        else 
        {
            if (!cnt[root]) 
            {
                dp[root] = (stop[root] == 1) ? 1 : 2;
                return;
            }
            for(int i = 0; i < 26; i++) if (trie[root][i]) if (dp[trie[root][i]] == 2) dp[root] = 2;
            if (!dp[root]) dp[root] = 1;
        }
    }
};

void solve() 
{
    int n;
    cin >> n;
    Trie t;
    for(int i = 1; i <= n; i++) 
    {
        string s;
        cin >> s;
        t.add(s, 1);
    }
    int m;
    cin >> m;
    for(int i = 1; i <= m; i++) 
    {
        string s;
        cin >> s;
        t.add(s, 2);
    }
    t.play(0, 1);
    cout << (dp[0] == 1 ? "Nina" : "Emilija") << endl;
}

signed main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    // cin >> t;
    for(int i = 1; i <= t; i++) solve();
}

• 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