oj.uz

Submission #405681

# Submission time Handle Problem Language Result Execution time Memory
405681 2021-05-16T17:33:15 Z souvenir_vayne Vlak (COCI20_vlak) C++14
70 / 70
 25 ms 23244 KB 
#include<bits/stdc++.h>

using namespace std;

struct trie {
    trie *a[26];
    bool can[26];
    int sz = 0;
};

trie *x = new trie();

bool dfs(trie *u) {

    bool ans = (u->sz) & 1;
    ans = !ans;

    for(int i = 0; i < 26; i++) {
        if(!(u->can[i])) continue;
        if( (u->sz & 1) ) {
            ans = max(ans, dfs(u->a[i]));
            if(ans)
                return 1;
        }
        else {
            ans = min(ans, dfs(u->a[i]));
            if(!ans)
                return 0;
        }
    }
    return ans;
}

int32_t main() {


    int n;
    cin >> n;

    while(n--) {

        string s;
        cin >> s;

        trie *aux = x;
        for(int i = 0; i < s.size(); i++) {
            if(aux->a[s[i] - 'a'] == NULL)
                aux->a[s[i] - 'a'] = new trie();
            if(i%2 == 0)
                aux->can[s[i] - 'a'] = 1;
            aux = aux->a[s[i] - 'a'];
            aux->sz = i+1;
        }
    }


    cin >> n;

    while(n--) {

        string s;
        cin >> s;

        trie *aux = x;
        for(int i = 0; i < s.size(); i++) {
            if(aux->a[s[i] - 'a'] == NULL)
                aux->a[s[i] - 'a'] = new trie();
            if(i & 1)
                aux->can[s[i] - 'a'] = 1;
            aux = aux->a[s[i] - 'a'];
            aux->sz = i+1;
        }

    }

    cout << (dfs(x) ? "Emilija" : "Nina") << endl;

}

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:46:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(int i = 0; i < s.size(); i++) {
      |                        ~~^~~~~~~~~~
Main.cpp:65:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for(int i = 0; i < s.size(); i++) {
      |                        ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 21708 KB Output is correct
2 Correct 24 ms 20428 KB Output is correct
3 Correct 25 ms 19204 KB Output is correct
4 Correct 24 ms 21196 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 22236 KB Output is correct
2 Correct 24 ms 23244 KB Output is correct
3 Correct 22 ms 21332 KB Output is correct
4 Correct 22 ms 21708 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 20916 KB Output is correct
2 Correct 22 ms 20412 KB Output is correct
3 Correct 23 ms 21068 KB Output is correct
4 Correct 24 ms 22396 KB Output is correct