oj.uz

Submission #953198

# Submission time Handle Problem Language Result Execution time Memory
953198 2024-03-25T16:53:31 Z AverageAmogusEnjoyer Vlak (COCI20_vlak) C++17
70 / 70
 8 ms 9952 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i,T j) { return i > j ? i = j, true : false; }
template<class T> bool cmax(T &i,T j) { return i < j ? i = j, true : false; }

constexpr int nax = 4e5;
int trie[nax][26];
bool who[nax][2];

bool dfs(int x,int turn) { // se vince il giocare 'turn' giocando da x
    for (int i=0;i<26;i++) {
        if (!trie[x][i]) { continue; }
        int y = trie[x][i];
        if (who[y][turn] && !dfs(y,turn^1)) { 
            return true;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int cnt = 1;
    while(n--) {
        string s;
        cin >> s;
        int u = 0;
        for (auto &c: s) {
            if (!trie[u][c-'a']) { trie[u][c-'a']=cnt++; }
            u = trie[u][c-'a'];
            who[u][0]=true;
        }
    }
    int m;
    cin >> m;
    while(m--) {
        string s;
        cin >> s;
        int u = 0;
        for (auto &c: s) {
            if (!trie[u][c-'a']) { trie[u][c-'a']=cnt++; }
            u = trie[u][c-'a'];
            who[u][1]=true;
        }
    }
    cout << (dfs(0,0) ? "Nina" : "Emilija") << "\n";
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 0 ms 468 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9304 KB Output is correct
2 Correct 6 ms 8796 KB Output is correct
3 Correct 6 ms 8320 KB Output is correct
4 Correct 8 ms 9052 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9564 KB Output is correct
2 Correct 6 ms 9952 KB Output is correct
3 Correct 6 ms 9188 KB Output is correct
4 Correct 7 ms 9308 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9052 KB Output is correct
2 Correct 6 ms 8796 KB Output is correct
3 Correct 6 ms 9200 KB Output is correct
4 Correct 7 ms 9564 KB Output is correct