oj.uz

Submission #825760

# Submission time Handle Problem Language Result Execution time Memory
825760 2023-08-15T07:47:12 Z taitruong270 Vlak (COCI20_vlak) C++17
30 / 70
 23 ms 23300 KB 
/*==============================================================================================================
         __                    __                                             _____     ______    _______
        |  |                  |  |                                           /  __ \   / _____|  / ______|     
      __|  |__              __|  |__                                         |_|  | |  | |       | |  
     |__|   __|            |__|   __|                                             | |  | |____   | |_____ 
        |  |    _____   _     |  |    ____  __  __  ____    _____    _____       / /   \ ___  \  |  ___  \
        |  |   /  _  \ | |    |  |   /  _/ | | | | /  _  \ /  __ \  /  _  \     / /         | |  | |   | |
        |  |_  | |_| | | |    |  |_  | |   | |_| | | |_| | | |  | | | |_| |    / /___   ____| |  | |___| |
        \____\ \____/| |_|    \____\ |_|   \_____/ \_____/ |_|  |_| \____ |   |______| |______/  \_______/
                                                                        | |
                                                                      __/ |
                                                                     |___/  
                                        Pratice, practice, and practice
                                       Where is the bug, delete it there
                                     Try, try, try again until you succeed
I hated every minute of training, but I said, 'Don't quit. Suffer now and live the rest of your life as a champion.' - Mohamed Ali 
                              You may not be the best, but must be the most effort
     Even the things and people you like, you don't have the courage to take, you are destined to be a failure.
                                           Difficult means more time
                                         Pain + Reflection = Progress 
==============================================================================================================*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define endl '\n'
const ll mod = 1e9+7;
const ll inf = 1e18;

struct Trie 
{
    struct node 
    {
        ll cnt[2], isEnd, level, win; //so tien to va so luong xau ket thuc 
        node *child[26];

        node()
        {
            cnt[0]=cnt[1]=0;
            isEnd=false;
            level=0;
            win=-1;
            for (ll i=0; i<26; i++) child[i]=NULL;
        }
    };
    node *root=new node();
    string tmp;

    Trie() {}

    void insert(string s, ll type)
    {
        ll n=s.size(), l=0;
        node *p=root;
        p->cnt[type]+=1;
        for (ll i=0; i<n; i++)
        {
            ll nxt=s[i]-'a';
            if (p->child[nxt]==NULL) p->child[nxt]=new node();
            p=p->child[nxt];
            p->cnt[type]+=1;
            p->level=++l;
        }
        p->isEnd+=1;
    }

    bool dp(node *p)
    {
        if (p->win!=-1) return p->win;
        ll turn=p->level%2;
        p->win=0;
        for (ll i=0; i<26; i++) if (p->child[i]!=NULL)
        {
            if (dp(p->child[i])==0) p->win=1;
        }
        return p->win;
    }

    void travel(node *p, string s)
    {
        if (p==NULL) return;
        cout<<s<<" "<<p->win<<endl;
        for (ll i=0; i<26; i++) if (p->child[i]!=NULL) travel(p->child[i], s+char('a'+i));
    }

    void debug() { travel(root, ""); }
};

void solve()
{
    Trie trie;
    ll n; cin>>n;
    for (ll i=0; i<n; i++)
    {
        string s; cin>>s;
        trie.insert(s, 1);
    }
    ll m; cin>>m;
    for (ll i=0; i<m; i++)
    {
        string s; cin>>s;
        trie.insert(s, 0);
    }
    if (trie.dp(trie.root)) cout<<"Nina";
    else cout<<"Emilija";
    // cout<<endl;
    // trie.debug();
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    clock_t start = clock();
    //#ifndef ONLINE_JUDGE
    //freopen("_input.txt", "r", stdin);
    //freopen("_output.txt", "w", stdout);
    //#endif
    solve();
    clock_t end = clock();
    cerr<<"Time: "<<fixed<<setprecision(10)<<double(end-start)/double(CLOCKS_PER_SEC)<<"\n";
    return 0;
}

Compilation message

Main.cpp: In member function 'bool Trie::dp(Trie::node*)':
Main.cpp:70:12: warning: unused variable 'turn' [-Wunused-variable]
   70 |         ll turn=p->level%2;
      |            ^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Incorrect 1 ms 580 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 448 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Incorrect 1 ms 468 KB Output isn't correct
4 Halted 0 ms 0 KB -

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 596 KB Output is correct
3 Correct 1 ms 496 KB Output is correct
4 Correct 1 ms 468 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 21796 KB Output is correct
2 Incorrect 20 ms 20436 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 22312 KB Output is correct
2 Correct 23 ms 23300 KB Output is correct
3 Correct 17 ms 21332 KB Output is correct
4 Correct 18 ms 21808 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 21076 KB Output is correct
2 Incorrect 23 ms 20436 KB Output isn't correct
3 Halted 0 ms 0 KB -