oj.uz

Submission #1006575

# Submission time Handle Problem Language Result Execution time Memory
1006575 2024-06-24T03:54:39 Z vjudge1 Vlak (COCI20_vlak) C++17
70 / 70
 20 ms 61688 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
int n, m, sz = 1, nxt[3][N][26], lvl;
bool win[N];

void add(string s, int id){
    int cur = 0;
    for (int i = 0; i < s.size(); i ++){
        char c = s[i];
        int e = s[i] - 'a';

        if (nxt[2][cur][e] == -1){
            nxt[2][cur][e] = sz;
            nxt[id][cur][e] = sz;
            sz++;
        }
        else
            nxt[id][cur][e] = nxt[2][cur][e];
        
        // cout << cur << " -- " << c << " -- ";
        cur = nxt[2][cur][e];
        // cout << cur << endl;
    }
}

void dfs(int v){
    bool leaf = 1;
    for (int e = 0; e < 26; e ++){
        if (nxt[2][v][e] == -1) continue;
        int u = nxt[2][v][e];
        
        lvl++;
        dfs(u);
        lvl++;

        if (nxt[lvl % 2][v][e] != -1){
            leaf = 0;
            win[v] |= !win[u];
        }
    }

    if (leaf)
        win[v] = 0;

}

int main(){
    memset(nxt, -1, sizeof nxt);

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

    dfs(0);

    cout << (win[0] ? "Nina" : "Emilija") << endl;
}

Compilation message

Main.cpp: In function 'void add(std::string, int)':
Main.cpp:10:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for (int i = 0; i < s.size(); i ++){
      |                     ~~^~~~~~~~~~
Main.cpp:11:14: warning: unused variable 'c' [-Wunused-variable]
   11 |         char c = s[i];
      |              ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 61276 KB Output is correct
2 Correct 8 ms 61416 KB Output is correct
3 Correct 8 ms 61276 KB Output is correct
4 Correct 7 ms 61276 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 61276 KB Output is correct
2 Correct 9 ms 61400 KB Output is correct
3 Correct 8 ms 61272 KB Output is correct
4 Correct 8 ms 61276 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 61276 KB Output is correct
2 Correct 8 ms 61424 KB Output is correct
3 Correct 8 ms 61272 KB Output is correct
4 Correct 9 ms 61344 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 61272 KB Output is correct
2 Correct 8 ms 61356 KB Output is correct
3 Correct 8 ms 61272 KB Output is correct
4 Correct 8 ms 61276 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 61688 KB Output is correct
2 Correct 20 ms 61520 KB Output is correct
3 Correct 20 ms 61532 KB Output is correct
4 Correct 20 ms 61512 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 61528 KB Output is correct
2 Correct 18 ms 61512 KB Output is correct
3 Correct 18 ms 61532 KB Output is correct
4 Correct 18 ms 61600 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 61532 KB Output is correct
2 Correct 18 ms 61532 KB Output is correct
3 Correct 18 ms 61532 KB Output is correct
4 Correct 19 ms 61532 KB Output is correct