oj.uz

Submission #453798

# Submission time Handle Problem Language Result Execution time Memory
453798 2021-08-04T21:52:34 Z RGBB Vlak (COCI20_vlak) C++14
70 / 70
 17 ms 21804 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int MAXN=100;
const int MAXC=2*1e5+5;
int n,m;
string inp;
//0-Nina, 1-Emilija
int en;
int trie[MAXC][27];//0 to 25 letters, 26 parent
bool win[MAXC][2];
void update(string s,int id)
{
    int pos=0;
    for(int i=0;i<s.length();i++)
    {
        if(trie[pos][s[i]-'a']==-1)
        {
            trie[pos][s[i]-'a']=en;
            trie[en++][26]=pos;
        }
        pos=trie[pos][s[i]-'a'];
        win[pos][id]=true;
    }
}
void solve(int pos)
{
    for(int i=en-1;i>0;i--)
    {
        if(win[i][0])win[trie[i][26]][1]=false;
        if(win[i][1])win[trie[i][26]][0]=false;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    memset(trie,-1,sizeof(trie));
    win[0][0]=true;
    win[0][1]=true;
    en=1;

    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>inp;
        update(inp,0);
    }
    cin>>m;
    for(int i=0;i<m;i++)
    {
        cin>>inp;
        update(inp,1);
    }
    solve(0);
    if(!win[0][1])cout<<"Nina\n";
    else cout<<"Emilija\n";
}

Compilation message

Main.cpp: In function 'void update(std::string, int)':
Main.cpp:15:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int i=0;i<s.length();i++)
      |                 ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 21452 KB Output is correct
2 Correct 9 ms 21384 KB Output is correct
3 Correct 9 ms 21452 KB Output is correct
4 Correct 9 ms 21368 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 21456 KB Output is correct
2 Correct 9 ms 21452 KB Output is correct
3 Correct 10 ms 21452 KB Output is correct
4 Correct 9 ms 21452 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 21800 KB Output is correct
2 Correct 15 ms 21772 KB Output is correct
3 Correct 14 ms 21804 KB Output is correct
4 Correct 16 ms 21728 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21708 KB Output is correct
2 Correct 14 ms 21712 KB Output is correct
3 Correct 13 ms 21780 KB Output is correct
4 Correct 13 ms 21708 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21724 KB Output is correct
2 Correct 15 ms 21784 KB Output is correct
3 Correct 14 ms 21720 KB Output is correct
4 Correct 17 ms 21720 KB Output is correct