Submission #377464

#	Time	Username	Problem	Language	Result	Execution time	Memory
377464		VEGAnn	Vlak (COCI20_vlak)	C++14	70 / 70	315 ms	10696 KiB

Main

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define PB push_back
#define all(x) x.begin(),x.end()
#define i2 array<int,2>
#define i3 array<int,3>
using namespace std;
typedef long long ll;
const int oo = 2e9;
const int N = 200100;
const int PW = 10;
const int HPW = 233;
const int md = int(1e9) + 7;
string s;
int n[2], cnt = 1, go[N][26], mrk[N];
int f[N][2];

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

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    mrk[1] = 3;

    for (int tp = 0; tp < 2; tp++){
        cin >> n[tp];

        for (int i = 0; i < n[tp]; i++){
            cin >> s;

            int loc = 1;

            for (int j = 0; j < sz(s); j++){
                int ch = (s[j] - 'a');

                if (go[loc][ch] == 0){
                    go[loc][ch] = ++cnt;
                }

                loc = go[loc][ch];
                mrk[loc] |= (1 << tp);
            }
        }
    }

    /// 0 -- lose
    /// 1 -- win

    for (int i = cnt; i > 0; i--)
    for (int tp = 0; tp < 2; tp++){
        f[i][tp] = 0;

        for (int ch = 0; ch < 26; ch++){
            if (go[i][ch] == 0) continue;

            int nw = go[i][ch];

            if (!(mrk[nw] & (1 << tp))) continue;

            if (!f[nw][tp ^ 1])
                f[i][tp] = 1;
        }
    }

    if (f[1][0])
        cout << "Nina";
    else cout << "Emilija\n";

    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