oj.uz

Submission #378815

# Submission time Handle Problem Language Result Execution time Memory
378815 2021-03-17T05:10:30 Z Araragi Vlak (COCI20_vlak) C++17
70 / 70
 42 ms 20460 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("00")
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
ll time() {return chrono::system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
const int inf = 1e9;
const ll inf64 = 1e18;
#define ft first
#define fin(x) ifstream cin("x.in");
#define fout(x) ofstream cout("x.out");
#define sd second
#define pb push_back
#define sz(x) (int)x.size()

struct trie
{
    trie *nxt[26]{};
    bool who[2]{}, ok{};

    void add(char* now, int n, int wh)
    {
        who[wh] = true;

        if (!n)
            return;

        auto& to = nxt[*now - 'a'];

        if (!to)
            to = new trie();

        to->add(now + 1, n - 1, wh);
    }

    void play(int whoMove)
    {
        ok = whoMove ^ 1;
        for (int i = 0; i < 26; i++)
        {
            if (!nxt[i])
                continue;
            nxt[i]->play(whoMove ^ 1);
            if (nxt[i]->ok == whoMove && nxt[i]->who[whoMove])
                ok = whoMove;
        }
    }
};

int main(){
   ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

   trie root;

   int n;
   cin >> n;

   for (int i = 0; i < n; i++)
   {
        string s;
        cin >> s;
        root.add(&s[0], (int)s.size(), 0);
   }

   int m;
   cin >> m;

   for (int i = 0; i < m; i++)
   {
       string s;
       cin >> s;
       root.add(&s[0], (int)s.size(), 1);
   }

   root.play(0);

   cout << (root.ok ? "Emilija" : "Nina");
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 19180 KB Output is correct
2 Correct 38 ms 18020 KB Output is correct
3 Correct 33 ms 17004 KB Output is correct
4 Correct 36 ms 18668 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 19564 KB Output is correct
2 Correct 35 ms 20460 KB Output is correct
3 Correct 32 ms 18796 KB Output is correct
4 Correct 37 ms 19180 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 18540 KB Output is correct
2 Correct 33 ms 18028 KB Output is correct
3 Correct 33 ms 18540 KB Output is correct
4 Correct 36 ms 19692 KB Output is correct