oj.uz

Submission #1003200

# Submission time Handle Problem Language Result Execution time Memory
1003200 2024-06-20T07:44:50 Z amin_2008 Vlak (COCI20_vlak) C++17
70 / 70
 23 ms 21340 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 860 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 19908 KB Output is correct
2 Correct 18 ms 18652 KB Output is correct
3 Correct 15 ms 17756 KB Output is correct
4 Correct 17 ms 19548 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 20316 KB Output is correct
2 Correct 18 ms 21340 KB Output is correct
3 Correct 18 ms 19616 KB Output is correct
4 Correct 15 ms 19804 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 19324 KB Output is correct
2 Correct 14 ms 18780 KB Output is correct
3 Correct 17 ms 19292 KB Output is correct
4 Correct 15 ms 20572 KB Output is correct