oj.uz

Submission #692251

# Submission time Handle Problem Language Result Execution time Memory
692251 2023-02-01T08:56:30 Z Huy Vlak (COCI20_vlak) C++17
70 / 70
 43 ms 29420 KB 
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#pragma GCC tarGet ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC tarGet("avx,avx2,fma")
using namespace std;
using ll = long long;
const int mod = 1e9+7;
const int maxN = 3e5+5;
const int N = 3e5;
const ll infty = 1e16;
void InputFile()
{
    freopen("CONC.inp","r",stdin);
    freopen("CONC.out","w",stdout);
    //freopen("test.out","r",stdin);
}

int n,m;

struct TNode
{
    int child[26];
    int type;
    int depth;
};
vector<TNode> Tree;

int dp[maxN];

void add_node()
{
    TNode tmp;
    for(int i = 0;i < 26;i++)
    {
        tmp.child[i] = -1;
    }
    tmp.type = 0;
    tmp.depth = 0;
    Tree.push_back(tmp);
}

void Insert(string s,int p)
{
    int it = 0;
    for(int i = 0;i < s.size();i++)
    {
        if(Tree[it].child[s[i]-'a'] == -1)
        {
            add_node();
            Tree[it].child[s[i]-'a'] = Tree.size() - 1;
        }
        int fa = it;
        it = Tree[it].child[s[i]-'a'];
        Tree[it].type |= p;
        Tree[it].depth = (Tree[fa].depth + 1) % 2;
    }
}

void DP(int u)
{
    for(int i = 0;i < 26;i++)
    {
        if(Tree[u].child[i] == -1) continue;
        int v = Tree[u].child[i];
        if(Tree[v].type & (1 << Tree[u].depth))
        {
            DP(v);
            dp[u] = max(dp[u],dp[v] ^ 1);
        }
    }
}

void Read()
{
    add_node();
    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        string s;
        cin >> s;
        Insert(s,1);
    }
    cin >> m;
    for(int i = 1;i <= m;i++)
    {
        string s;
        cin >> s;
        Insert(s,2);
    }
    DP(0);
    if(dp[0])
    {
        cout <<"Nina";
        return;
    }
    cout <<"Emilija";
}

void Solve()
{

}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //InputFile();
    //int sub_type;
    //cin >> sub_type;
    //Sieve();
    //Prepare();
    int test;
    //cin >> test;
    test = 1;
    while(test--)
        //for(int prc = 1; prc <= test; prc++)
    {
        Read();
        Solve();
        //Debug();
    }
}

Compilation message

Main.cpp:6: warning: ignoring '#pragma GCC tarGet' [-Wunknown-pragmas]
    6 | #pragma GCC tarGet ("avx2")
      | 
Main.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("O3")
      | 
Main.cpp:8: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    8 | #pragma GCC optimization ("unroll-loops")
      | 
Main.cpp:10: warning: ignoring '#pragma GCC tarGet' [-Wunknown-pragmas]
   10 | #pragma GCC tarGet("avx,avx2,fma")
      | 
Main.cpp: In function 'void Insert(std::string, long long int)':
Main.cpp:51:21: 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]
   51 |     for(int i = 0;i < s.size();i++)
      |                   ~~^~~~~~~~~~
Main.cpp: In function 'void InputFile()':
Main.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen("CONC.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     freopen("CONC.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 612 KB Output is correct
2 Correct 1 ms 884 KB Output is correct
3 Correct 1 ms 868 KB Output is correct
4 Correct 1 ms 628 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 29376 KB Output is correct
2 Correct 28 ms 29324 KB Output is correct
3 Correct 26 ms 29368 KB Output is correct
4 Correct 29 ms 29328 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 29372 KB Output is correct
2 Correct 26 ms 29384 KB Output is correct
3 Correct 24 ms 29372 KB Output is correct
4 Correct 28 ms 29420 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 29356 KB Output is correct
2 Correct 27 ms 29388 KB Output is correct
3 Correct 28 ms 29344 KB Output is correct
4 Correct 43 ms 29364 KB Output is correct