oj.uz

답안 #636639

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
636639 2022-08-29T20:37:53 Z Wael Vlak (COCI20_vlak) C++14
70 / 70
 27 ms 25428 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
#define F first
#define S second
#define endl '\n'
int const M = 1e6 + 10 , mod = 1e9 + 7;
ll n , T , Next[M][30] , vis[M][4] , Winner[M] , cnt = 1;
string s;

inline void Dfs(int node , int cur , int index) {

    vis[node][cur] = 1;
    if(index == s.size()) return;
    int Char = s[index] - 'a';
    if(!Next[node][Char]) Next[node][Char] = ++cnt;
    Dfs(Next[node][Char] , cur , index + 1);

}

inline void Get(int node , int dep) { //cout << "Node = " << node << endl;

    int have[4] = {0};
    for(int i = 0 ; i < 26 ; ++i) {
        if(Next[node][i]) {
            Get(Next[node][i] , dep + 1);
            have[Winner[Next[node][i]]] = 1;
        }
    }

    if(!have[1] && !have[2]) { //cout << "node = " << node << endl;
        if(dep % 2) Winner[node] = 2;
        else Winner[node] = 1;
        return;
    }

    if(!vis[node][1] || !vis[node][2]) {
        if(!vis[node][1]) Winner[node] = 2;
        else Winner[node] = 1;
        //cout << node << " " << vis[node][1] << " " << vis[node][2] << " " << Winner[node] << endl;
        return;
    }

    if(dep % 2) {
        if(have[1]) Winner[node] = 1;
        else Winner[node] = 2;
    }

    else {
        if(have[2]) Winner[node] = 2;
        else Winner[node] = 1;
    }
}

main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);

    cin >> n;
    for(int i = 1 ; i <= n ; ++i) {
        cin >> s;
        Dfs(1 , 1 , 0);
    }

    cin >> n;
    for(int i = 1 ; i <= n ; ++i) {
        cin >> s;
        Dfs(1 , 2 , 0);
    }

    Get(1 , 1);

    if(Winner[1] == 1) cout << "Nina" << endl;
    else cout << "Emilija" << endl;

    return 0;
}

Compilation message

Main.cpp: In function 'void Dfs(long long int, long long int, long long int)':
Main.cpp:15:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     if(index == s.size()) return;
      |        ~~~~~~^~~~~~~~~~~
Main.cpp: At global scope:
Main.cpp:56:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   56 | main() {
      | ^~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 580 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 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 596 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 584 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 596 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 580 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 596 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 23732 KB Output is correct
2 Correct 24 ms 22340 KB Output is correct
3 Correct 23 ms 21048 KB Output is correct
4 Correct 27 ms 23252 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 24340 KB Output is correct
2 Correct 25 ms 25428 KB Output is correct
3 Correct 23 ms 23376 KB Output is correct
4 Correct 22 ms 23764 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 22936 KB Output is correct
2 Correct 24 ms 22452 KB Output is correct
3 Correct 25 ms 22932 KB Output is correct
4 Correct 26 ms 24396 KB Output is correct