oj.uz

Submission #377464

# Submission time Handle Problem Language Result Execution time Memory
377464 2021-03-14T08:54:55 Z VEGAnn Vlak (COCI20_vlak) C++14
70 / 70
 315 ms 10696 KB 
#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.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 30 ms 520 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 10092 KB Output is correct
2 Correct 61 ms 9396 KB Output is correct
3 Correct 60 ms 8872 KB Output is correct
4 Correct 19 ms 9708 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 10220 KB Output is correct
2 Correct 20 ms 10696 KB Output is correct
3 Correct 18 ms 9836 KB Output is correct
4 Correct 271 ms 9964 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 9696 KB Output is correct
2 Correct 20 ms 9452 KB Output is correct
3 Correct 20 ms 9708 KB Output is correct
4 Correct 315 ms 10240 KB Output is correct