oj.uz

Submission #704939

# Submission time Handle Problem Language Result Execution time Memory
704939 2023-03-03T07:02:16 Z 1075508020060209tc Vlak (COCI20_vlak) C++14
70 / 70
 26 ms 20052 KB 
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
int n;int m;
int __id=1;
int nxt[30][500005];
int vis[2][500005];
int visb[500005];
void insa(string s){
int nw=1;
vis[0][nw]=1;
for(int i=0;i<s.size();i++){
    int v=s[i]-'a';
    if(nxt[v][nw]==0){
        nxt[v][nw]=++__id;
    }
    nw=nxt[v][nw];
    vis[0][nw]=1;
}
}
void insb(string s){
int nw=1;
vis[1][nw]=1;
for(int i=0;i<s.size();i++){
    int v=s[i]-'a';
    if(nxt[v][nw]==0){
        nxt[v][nw]=++__id;
    }
    nw=nxt[v][nw];
    vis[1][nw]=1;
}
}
int dp[500005];
void dfs(int nw,int plyr){
dp[nw]=1;
for(int i=0;i<=29;i++){
    if(nxt[i][nw]==0){continue;}
    int v=nxt[i][nw];
    if(vis[plyr^1][v]==0){continue;}
    dfs(v,plyr^1);
    if(dp[v]==1){
        dp[nw]=0;
    }
}
}


signed main(){
cin>>n;
for(int i=1;i<=n;i++){
    string s;
    cin>>s;
    insa(s);
}
cin>>m;
for(int i=1;i<=m;i++){
    string s;
    cin>>s;
    insb(s);
}
dfs(1,1);

/*
for(int i=1;i<=__id;i++){
    cout<<dp[i]<<" ";
}cout<<endl;
for(int i=1;i<=__id;i++){
    cout<<vis[0][i]<<" ";
}cout<<endl;
for(int i=1;i<=__id;i++){
    cout<<vis[1][i]<<" ";
}cout<<endl;*/

if(!dp[1]){
    cout<<"Nina\n";
}else{
    cout<<"Emilija";
}

}

Compilation message

Main.cpp: In function 'void insa(std::string)':
Main.cpp:15:14: 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]
   15 | for(int i=0;i<s.size();i++){
      |             ~^~~~~~~~~
Main.cpp: In function 'void insb(std::string)':
Main.cpp:27:14: 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]
   27 | for(int i=0;i<s.size();i++){
      |             ~^~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 18848 KB Output is correct
2 Correct 23 ms 17668 KB Output is correct
3 Correct 22 ms 16844 KB Output is correct
4 Correct 22 ms 18568 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 19288 KB Output is correct
2 Correct 21 ms 20052 KB Output is correct
3 Correct 20 ms 18772 KB Output is correct
4 Correct 21 ms 19068 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 18168 KB Output is correct
2 Correct 22 ms 17696 KB Output is correct
3 Correct 23 ms 18424 KB Output is correct
4 Correct 24 ms 19604 KB Output is correct