oj.uz

Submission #689440

# Submission time Handle Problem Language Result Execution time Memory
689440 2023-01-28T13:46:51 Z MON Vlak (COCI20_vlak) C++14
70 / 70
 26 ms 20388 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

struct Trie
{
    bool e[2]; bool dp; int depth = 0;
    Trie *next[26];
    void baga(string &s,int p,int c)
    {
        e[c] = 1;
        if(p == s.size()) return;
        if(!next[s[p] - 'a'])
            {
                next[s[p] - 'a'] = new Trie;
                next[s[p] - 'a']->depth = depth + 1;
            }

        next[s[p] - 'a']->baga(s,p + 1,c);
    }

    void din()
    {
        if(e[0] != e[1])
            {
                dp = e[0];
                return;
            }

         for(int l = 0 ; l < 26 ; l++)
            {
                if(!next[l]) continue;
                next[l]->din();
            }

        if(depth & 1)
            {
                for(int l = 0 ; l < 26 ; l++)
                {
                    if(!next[l]) continue;
                    if(!next[l]->dp)
                        {
                            dp = 0;
                            return;
                        }
                }

                dp = 1;
            }

        else
            {
                for(int l = 0 ; l < 26 ; l++)
                {
                    if(!next[l]) continue;
                    if(next[l]->dp)
                        {
                            dp = 1;
                            return;
                        }
                }

                dp = 0;
            }
    }
};


int main()
{
    int n,m;
    cin >> n ; string s;
    Trie *trie = new Trie;
    while(n--)
        {
            cin >> s;
            trie->baga(s,0,0);
        }

    cin >> m;
    while(m--)
        {
            cin >> s;
            trie->baga(s,0,1);
        }

    trie->din();
    string ans = trie->dp ? "Nina" : "Emilija";
    cout << ans;
}

Compilation message

Main.cpp: In member function 'void Trie::baga(std::string&, int, int)':
Main.cpp:14:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |         if(p == s.size()) return;
      |            ~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 560 KB Output is correct
4 Correct 1 ms 428 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 556 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 552 KB Output is correct
4 Correct 1 ms 468 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 432 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 424 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 19132 KB Output is correct
2 Correct 20 ms 17868 KB Output is correct
3 Correct 26 ms 16944 KB Output is correct
4 Correct 20 ms 18596 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 19540 KB Output is correct
2 Correct 18 ms 20388 KB Output is correct
3 Correct 17 ms 18772 KB Output is correct
4 Correct 17 ms 19020 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 18388 KB Output is correct
2 Correct 19 ms 17980 KB Output is correct
3 Correct 20 ms 18392 KB Output is correct
4 Correct 19 ms 19640 KB Output is correct