Submission #1153867

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153867		simuyu	Vlak (COCI20_vlak)	C++20	70 / 70	16 ms	17476 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long

class branch {
public:
    char c;
    vector<branch*> childs;
    map<char, int> cs; // char to index mapping, but it's index+1 to avoid being 0 which is false

    branch (char _c) {
        c = _c;
    }

    void display(string bef) {
        cout << bef << "+"  << c << endl;
        for (ll cidx=0; cidx<childs.size(); cidx++) {
            string t = "";
            t += bef;
            childs[cidx]->display(t+c);
        }
        if (!childs.empty()) cout << endl;
    }

    bool canwin(branch* other) {
        //cout << c << " CANWIN " << other->c << endl;
        // base case: no children, so no words to do.
        if (childs.empty()) return false; // lost

        for (ll cidx=0; cidx<childs.size(); cidx++) {
            // base case: i've this letter but other doesn't have
            int oidx = other->cs[childs[cidx]->c];
            if (oidx) {
                if (!(other->childs[oidx-1]->canwin(childs[cidx]))) {
                    // since enemy can't win, i win!!
                    return true;
                } // otherwise try again
            } else {
                // this is the base case. since enemy can't do anyt abt this, you win!
                return true;
            }
        }
        // couldn't win --> false
        return false;
    }


};

ll N, M;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    // nina
    branch nina = branch(' ');
    string t;
    cin >> N;
    for (ll i=0; i<N; i++) {
        branch* curr = &nina;

        cin >> t;
        //cout << t.size() << '"' << t << '"' << endl;
        for (ll j=0; j<t.size(); j++) {

            int temp = curr->cs[t[j]];
            //cout << "TEMP " << temp << endl;
            if (temp) {
                curr = curr->childs[temp-1];
                continue;
            }

            /*bool found = false;
            for (ll cidx=0; cidx<(curr->childs.size()); cidx++) {
                if (curr->childs[cidx]->c == t[j]) {
                    // found the node!
                    curr = curr->childs[cidx];
                    found = true;
                    break;
                }
            }*/

            //if (!found) {
            curr->childs.push_back(new branch(t[j]));
            curr->cs[t[j]] = curr->childs.size();
            curr = curr->childs[curr->childs.size() - 1 ];
            //}
        }
    }

    // debug: display the childs - recursive backtracking
    //nina.display("");


    // emilija
    /*branch emilija = branch(' ');
    cin >> M;
    for (ll i=0; i<M; i++) {
        branch* curr = &emilija;

        cin >> t;
        //cout << t.size() << '"' << t << '"' << endl;
        for (ll j=0; j<t.size(); j++) {
            bool found = false;
            for (ll cidx=0; cidx<(curr->childs.size()); cidx++) {
                if (curr->childs[cidx]->c == t[j]) {
                    // found the node!
                    curr = curr->childs[cidx];
                    found = true;
                    break;
                }
            }

            if (!found) {
                curr->childs.push_back(new branch(t[j]));
                curr->cs.insert(t[j]);
                curr = curr->childs[curr->childs.size() - 1 ];
            }
        }
    }*/


    // emilija
    branch emilija = branch(' ');
    cin >> M;
    for (ll i=0; i<M; i++) {
        branch* curr = &emilija;

        cin >> t;
        //cout << t.size() << '"' << t << '"' << endl;
        for (ll j=0; j<t.size(); j++) {

            int temp = curr->cs[t[j]];
            //cout << "TEMP " << temp << endl;
            if (temp) {
                curr = curr->childs[temp-1];
                continue;
            }

            /*bool found = false;
            for (ll cidx=0; cidx<(curr->childs.size()); cidx++) {
                if (curr->childs[cidx]->c == t[j]) {
                    // found the node!
                    curr = curr->childs[cidx];
                    found = true;
                    break;
                }
            }*/

            //if (!found) {
            curr->childs.push_back(new branch(t[j]));
            curr->cs[t[j]] = curr->childs.size();
            curr = curr->childs[curr->childs.size() - 1 ];
            //}
        }
    }



    // do DP
    if (nina.canwin(&emilija)) {
        cout << "Nina" << endl;
    } else {
        cout << "Emilija" << endl;
    }



    return 0;
}

• 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