oj.uz

Submission #917085

# Submission time Handle Problem Language Result Execution time Memory
917085 2024-01-27T06:37:39 Z Younis_Dwai Vlak (COCI20_vlak) C++14
70 / 70
 17 ms 44892 KB 
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define in insert
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define mid (l+r)/2
//#define all(v) v.begin(),v.end()
using namespace std;
const int M=1e9+7;
int trie[200001][26],nex=1,dp[200001][2];
bool can[200001][2];
void build(string s ,bool type){
     int i=0,v=0;
     while(i<s.size()){
         if(trie[v][s[i]-'a']!=-1) v=trie[v][s[i++]-'a'];
         else v=trie[v][s[i++]-'a']=nex++;
         can[v][type]=1;
     }
     return ;
}
bool rec(int node,int turn){
     bool leaf=1;
     for(int i=0;i<26;i++) if(trie[node][i]!=-1) leaf=0;
     if(leaf) return dp[node][turn]=0;
     bool res=0;
     for(int i=0;i<26;i++){
         if(trie[node][i]!=-1 && can[trie[node][i]][turn]==1 && rec(trie[node][i],1-turn)==0) res=1;
     }
     return dp[node][turn]=res;
}
int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    memset(trie,-1,sizeof trie);
    int n,m;
    cin>>n;
    for(int i=1;i<=n;i++){
        string x;cin>>x;
        build(x,0);
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        string x;cin>>x;
        build(x,1);
    }
    if(rec(0,0)==1) cout<<"Nina";
    else cout<<"Emilija";
    return 0;
}

Compilation message

Main.cpp: In function 'void build(std::string, bool)':
Main.cpp:17:13: 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]
   17 |      while(i<s.size()){
      |            ~^~~~~~~~~
Main.cpp: In function 'bool rec(long long int, long long int)':
Main.cpp:27:36: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   27 |      if(leaf) return dp[node][turn]=0;
      |                      ~~~~~~~~~~~~~~^~
Main.cpp:32:27: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   32 |      return dp[node][turn]=res;
      |             ~~~~~~~~~~~~~~^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 44376 KB Output is correct
2 Correct 7 ms 44380 KB Output is correct
3 Correct 8 ms 44380 KB Output is correct
4 Correct 7 ms 44380 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 44636 KB Output is correct
2 Correct 14 ms 44888 KB Output is correct
3 Correct 15 ms 44784 KB Output is correct
4 Correct 17 ms 44788 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 44780 KB Output is correct
2 Correct 13 ms 44884 KB Output is correct
3 Correct 13 ms 44632 KB Output is correct
4 Correct 14 ms 44636 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 44636 KB Output is correct
2 Correct 15 ms 44892 KB Output is correct
3 Correct 14 ms 44636 KB Output is correct
4 Correct 14 ms 44892 KB Output is correct