#include <bits/stdc++.h>
using namespace std;
#define int long long
#define faster ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define NMAX 200005
#define pb push_back
struct node{
bool ans[2];
unordered_map<char,int>next;
node(){
ans[1]=ans[0]=0;
next.clear();
}
};
vector<node>v;
int dp[NMAX];
int inicio;
int new_node(){
v.pb(node());
return v.size()-1;
}
bool solve(int x, int id){
if(id==0 && v[x].ans[id]==0)return false;
if(id==1 && v[x].ans[id]==0)return true;
if(dp[x]!=-2)return dp[x];
if(id==0){
dp[x]=false;
for(auto it:v[x].next){
if(solve(it.second, 1)==true){
dp[x]=true;
}
}
}
else{
dp[x]=true;
for(auto it:v[x].next){
if(solve(it.second, 0)==false){
dp[x]=false;
break;
}
}
}
return dp[x];
}
int32_t main(){ faster
int n;
cin>>n;
string s;
inicio=new_node();
while(n--){
cin>>s;
int x=inicio;
v[x].ans[0]=v[x].ans[1]=1;
for(auto it:s){
if(v[x].next.count(it)==0){
v[x].next[it]=new_node();
}
x=v[x].next[it];
v[x].ans[0]=1;
}
}
cin>>n;
while(n--){
cin>>s;
int x=inicio;
v[x].ans[0]=v[x].ans[1]=1;
for(auto it:s){
if(v[x].next.count(it)==0){
v[x].next[it]=new_node();
}
x=v[x].next[it];
v[x].ans[1]=1;
}
}
for(int i=0; i<NMAX; i++){
dp[i]=-2;
}
cout<<solve(0,0)<<"\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |