oj.uz

Submission #1021658

# Submission time Handle Problem Language Result Execution time Memory
1021658 2024-07-13T02:01:36 Z TrendBattles Vlak (COCI20_vlak) C++14
70 / 70
 17 ms 14684 KB 
#include <bits/stdc++.h>
using namespace std;
using lli = int64_t;

#define INFILE "vlak.inp"
#define OUTFILE "vlak.out"

const int MAX_AL = 26;
struct Node {
    int available = 0;
    int child[MAX_AL];

    Node() {
        memset(child, -1, sizeof child);
    }
};
vector <Node> trie(1);

void add(const string& s, int who) {
    int now = 0;
    for (char x : s) {
        int nxt = trie[now].child[x - 'a'];
        if (nxt == -1) {
            nxt = trie.size();
            trie[now].child[x - 'a'] = nxt;
            trie.emplace_back();
        }
        now = nxt;
        trie[now].available |= 1 << who;
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    if (fopen(INFILE, "r")) {
        freopen(INFILE, "r", stdin);
        freopen(OUTFILE, "w", stdout);
    }

    for (int i : {0, 1}) {
        int N; cin >> N;
        for (int t = 1; t <= N; ++t) {
            string S; cin >> S;
            add(S, i);
        }
    }

    vector <int> dp((int) trie.size() + 100, -1);
    
    auto DP = [&] (auto self, int u, int turn) -> int {
        int& now = dp[u];
        if (now != -1) return now;

        now = 0;
        for (int i = 0; i < 26; ++i) {
            if (trie[u].child[i] == -1) continue;

            int v = trie[u].child[i];
            if ((trie[v].available >> turn & 1) == 0) continue;

            now |= not self(self, v, turn ^ 1);
        }
        return now;
    };
    cout << (DP(DP, 0, 0) ? "Nina" : "Emilija");
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen(INFILE, "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen(OUTFILE, "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 604 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 1 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14540 KB Output is correct
2 Correct 13 ms 14684 KB Output is correct
3 Correct 12 ms 14536 KB Output is correct
4 Correct 15 ms 14540 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14536 KB Output is correct
2 Correct 12 ms 14540 KB Output is correct
3 Correct 11 ms 14660 KB Output is correct
4 Correct 17 ms 14536 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14536 KB Output is correct
2 Correct 12 ms 14536 KB Output is correct
3 Correct 13 ms 14540 KB Output is correct
4 Correct 11 ms 14540 KB Output is correct