제출 #855823

#제출 시각아이디문제언어결과실행 시간메모리
855823GoldLightVlak (COCI20_vlak)C++17
70 / 70
16 ms22620 KiB
#include <bits/stdc++.h> using namespace std; void fast(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);} struct trie{ trie *ch[26]; trie(){ for(int i=0; i<26; i++) ch[i]=NULL; } }root[2]; void add(string &s, int k){ trie *now=&root[k]; for(int i=0; i<(int)s.size(); i++){ if(!now->ch[s[i]-'a']) now->ch[s[i]-'a']=new trie(); now=now->ch[s[i]-'a']; } } bool dfs(trie *a, trie *b, int k){ bool ans; if(k&1){ ans=0; for(int i=0; i<26; i++){ if(a->ch[i] && b->ch[i]) ans|=dfs(a->ch[i], b->ch[i], k+1); else if(a->ch[i]){ ans=1; break; } } } else{ ans=1; for(int i=0; i<26; i++){ if(a->ch[i] && b->ch[i]) ans&=dfs(a->ch[i], b->ch[i], k+1); else if(b->ch[i]){ ans=0; break; } } } return ans; } int main(){ fast(); int n; cin>>n; for(int i=1; i<=n; i++){ string s; cin>>s; add(s, 0); } int m; cin>>m; for(int i=1; i<=m; i++){ string s; cin>>s; add(s, 1); } if(dfs(&root[0], &root[1], 1)) cout<<"Nina"; else cout<<"Emilija"; } /* struct trie{ bool val; trie *ch[26]; trie(){ val=0; for(int i=0; i<26; i++) ch[i]=NULL; } }root; void add(string &s){ trie *now=&root; for(int i=0; i<(int)s.size(); i++){ if(!now->ch[s[i]-'a']) now->ch[s[i]-'a']=new trie(); now=now->ch[s[i]-'a']; } now->val=1; } int main(){ fast(); int n, m; cin>>n>>m; string s; cin>>s; for(int i=1; i<=m; i++){ string t; cin>>t; add(t); } string t=""; int ans=0; trie *now=&root; for(int i=0; i<n; i++){ if(!now->ch[s[i]-'a']){ t.clear(); now=&root; } if(now->ch[s[i]-'a']){ now=now->ch[s[i]-'a']; if(now->val){ ans++; t.clear(); now=&root; } else t+=s[i]; } } cout<<ans; } */ /* #define int long long const int N=5e3, NN=1e6, mod=1e9+7; int dp[N+1]; struct trie{ bool val; trie *ch[26]; trie(){ val=0; for(int i=0; i<26; i++) ch[i]=NULL; } }root; void add(string &s){ trie *now=&root; for(int i=(int)s.size()-1; i>=0; i--){ if(!now->ch[s[i]-'a']) now->ch[s[i]-'a']=new trie(); now=now->ch[s[i]-'a']; } now->val=1; } vector<int> v; void f(string &s){ trie *now=&root; for(int i=(int)s.size()-1; i>=0; i--){ int c=s[i]-'a'; if(!now->ch[c]) return; now=now->ch[c]; if(now->val) v.push_back(i); } } // int now=1, trie[NN+1][26], exi[NN+1], word[NN+1]; // void add(string &s){ // int id=0; // for(int i=s.size()-1; i>=0; i--){ // if(!exi[trie[id][s[i]-'a']]){ // trie[id][s[i]-'a']=now++; // exi[now-1]=1; // } // id=trie[id][s[i]-'a']; // } // word[id]=1; // } // vector<int> v; // void f(string &s){ // int id=0; // for(int i=s.size()-1; i>=0; i--){ // if(!exi[trie[id][s[i]-'a']]) return; // id=trie[id][s[i]-'a']; // if(word[id]) v.push_back(i); // } // } signed main(){ fast(); string s; cin>>s; int n=(int)s.size(), k; cin>>k; for(int i=1; i<=k; i++){ string t; cin>>t; add(t); } string t=""; dp[0]=1; for(int i=1; i<=n; i++){ t+=s[i-1]; v.clear(); f(t); for(auto j:v) dp[i]+=dp[j]; dp[i]%=mod; } cout<<dp[n]; //for(int i=0; i<=n; i++) cout<<dp[i]<<' '; } */ //Trie /* const int LOG=30; struct trie { int val; trie *ch[2]; // [26] trie() { val = 0; ch[0] = NULL; ch[1] = NULL; } } root; void add(int x) { trie *now = &root; now->val++; for (int i=LOG-1;i>=0;i--) { if (!now->ch[(x>>i)&1]) { now->ch[(x>>i)&1] = new trie(); } now = now->ch[(x>>i)&1]; now->val++; } } int main() { int a = 5, b = 7; int *c, *d; c = &a; cout << *c << endl; a = 3; cout << *c << endl; *c = 6; cout << a << endl; d = c; (*d)++; cout << *c << endl; c = &b; *c = 4; cout << *d << endl; (*d).val d->val *d.val return 0; } */ /* vector<int> manacher(string s){ int n=s.size(), l=0, r=0; vector<int> c(n+2); s='^'+s+'#'; for(int i=1; i<=n; i++){ if(i<r) c[i]=min(r-i, c[l+r-i]); while(s[i-c[i]]==s[i+c[i]]) c[i]++; if(i+c[i]>r){ l=i-c[i], r=i+c[i]; } } return c; } string solve(string s){ int n=s.size(); int l=0, r=n-1; while(l<r && s[l]==s[r]) l++, r--; if(r<=l) return s; l--, r++; string news=""; for(int i=0; i<n; i++) news+=string("#")+s[i]; news+='#'; auto c=manacher(news); int ans=0, idx=0, m=news.size(), cek; for(int i=1; i<=m; i++){ int ki=(i-c[i]+2)/2-1, ka=(i+c[i]-2)/2-1; if(ki-1<=l && ka+1<r){ int ov=l+1-(l-(ki-1)); if(c[i]-1+2*ov>ans){ ans=c[i]-1+2*ov; idx=i; cek=0; } } else if(ka+1>=r && ki-1>l){ int ov=l+1-(ka+1-r); if(c[i]-1+2*ov>ans){ ans=c[i]-1+2*ov; idx=i; cek=1; } } //cout<<news[i-1]<<' '<<c[i]<<'\n'; } // cout<<ans<<' '<<idx<<'\n'; int ki=(idx-c[idx]+2)/2-1, ka=(idx+c[idx]-2)/2-1; string t=""; if(!cek){ int ov=(l-(ki-1)); t+=s.substr(0, l+1-ov+c[idx]-1); if(r+ov<n) t+=s.substr(r+ov, l+1-ov); } else{ int ov=(ka+1-r); if(l-ov>=0) t+=s.substr(0, l+1-ov); t+=s.substr(ki, (l+1-ov)+c[idx]-1); } return t; } int main(){ fast(); int teskes; cin>>teskes; while(teskes--){ string s; cin>>s; string x=solve(s); reverse(s.begin(), s.end()); string y=solve(s); if(x.size()>=y.size()) cout<<x; else cout<<y; cout<<'\n'; } } */ /* vector<int> manacher(string s){ int n=s.size(), l=0, r=0; vector<int> c(n+2); s='^'+s+'#'; for(int i=1; i<=n; i++){ if(i<r) c[i]=min(r-i, c[l+r-i]); while(s[i-c[i]]==s[i+c[i]]) c[i]++; if(i+c[i]>r){ l=i-c[i], r=i+c[i]; } } return c; } void solve(string s){ int n=s.size(); string news=""; for(int i=0; i<n; i++) news+=string("#")+s[i]; news+='#'; auto c=manacher(news); int ans=0, idx=0, m=news.size(); for(int i=1; i<=m; i++){ if(c[i]-1>ans){ ans=c[i]-1; idx=(i-c[i]+2)/2-1; } } cout<<s.substr(idx, ans); } int main(){ fast(); string s; cin>>s; solve(s); } */ //Manacher's Algo /* vector<int> manacher_odd(string s){ int n=s.size(), l=0, r=0; s='^'+s+'#'; vector<int> c(n+2); for(int i=1; i<=n; i++){ if(i<r) c[i]=min(r-i, c[l+(r-i)]); while(s[i-c[i]]==s[i+c[i]]) c[i]++; if(i+c[i]>r){ l=i, r=i+c[i]; } } return c; } vector<int> manacher_even(string s){ int n=s.size(); string news=""; for(int i=0; i<n; i++){ news+=string("#")+s[i]; } return manacher_odd(news+'#'); } int main(){ fast(); string s; cin>>s; auto co=manacher_odd(s), ce=manacher_even(s); } */ /* int main(){ fast(); string s; cin>>s; int n=s.size(), l=0, r=0; int obelix=0, suff=0; vector<int> z(n); for(int i=1; i<n; i++){ if(i<r) z[i]=min(r-i, z[i-l]); while(z[i]+i<n && s[z[i]]==s[z[i]+i]) z[i]++; if(i+z[i]>r){ l=i, r=i+z[i]; } obelix=max(obelix, z[i]-(z[i]+i==n)); if(z[i]+i==n && z[i]<=obelix) suff=max(suff, z[i]); } if(suff) cout<<s.substr(0, suff); else cout<<"Just a legend"; } */ //Z-Algo /* vector<int> z_f(string &s){ int n=s.size(), l=0, r=0; vector<int> z(n); for(int i=1; i<n; i++){ if(i<r){ z[i]=min(r-i, z[i-l]); } while(z[i]+i<n && s[z[i]]==s[z[i]+i]) z[i]++; if(i+z[i]>r){ l=i, r=i+z[i]; } cout<<z[i]<<' '; } cout<<'\n'; return z; } int main(){ string s; cin>>s; auto z=z_f(s); //for(auto &i:z) cout<<i<<' '; } */ /* const int N=6000; int a[N+5], b[N+1]; void f(string &s, int *c){ int j=0; for(int i=1; i<s.size(); i++){ while(j && s[i]!=s[j]) j=c[j-1]; if(s[i]==s[j]) j++; c[i]=j; } } tuple<int,int,int> solve(string &s, string &t, bool rev){ int n=s.size(), m=t.size(); tuple<int,int,int> ans={0, 0, 0}; string t2=t; reverse(t2.begin(), t2.end()); for(int i=0; i<n; i++){ string s1=s.substr(0, i), s2=s.substr(i, n-i); reverse(s1.begin(), s1.end()); s1+='#'+t, s2+='#'+t2; f(s1, a); f(s2, b); for(int j=1; j<=m; j++){ ans=max(ans, {a[i+j]+b[n+m-i-j], i-a[i+j], rev? m-j-b[n+m-i-j] : j-a[i+j]}); } } return ans; } int main(){ fast(); string s, t; cin>>s>>t; auto ans=solve(s, t, 0); reverse(t.begin(), t.end()); ans=max(ans, solve(s, t, 1)); cout<<get<0>(ans)<<'\n'<<get<1>(ans)<<' '<<get<2>(ans); } */ /* vector<int> f1(string &s, string &t){ int n=s.size(), m=t.size(), j=0; vector<int> a(n), b(m); for(int i=1; i<n; i++){ while(j>0 && s[i]!=s[j]) j=a[j-1]; if(s[i]==s[j]) j++; a[i]=j; } j=0; for(int i=0; i<m; i++){ while(j==n || (j>0 && s[j]!=t[i])) j=a[j-1]; if(s[j]==t[i]) j++; b[i]=j; } return b; } vector<int> f2(string &s, string &t){ int n=s.size(), m=t.size(), j=0; vector<int> a(n), b(m); for(int i=1; i<n; i++){ while(j>0 && s[i]!=s[j]) j=a[j-1]; if(s[i]==s[j]) j++; a[i]=j; } j=0; for(int i=m-1; i>=0; i--){ while(j==n || (j>0 && s[j]!=t[i])) j=a[j-1]; if(s[j]==t[i]) j++; b[i]=j; } return b; } int main(){ fast(); string s, t1, t2; cin>>s>>t1; t2=t1; reverse(t2.begin(), t2.end()); int n=s.size(), m=t1.size(); int ki=1, ka=n, ans, j1, j2; while(ki<=ka){ int k=(ki+ka)/2; bool cek=false; for(int l=0; l+k-1<n; l++){ if(cek) break; if(k>m){ cek=true; break; } string s1=s.substr(l, k); string s2=s1; reverse(s2.begin(), s2.end()); auto val1=f1(s1, t1), val2=f2(s2, t1), val3=f1(s1, t2), val4=f2(s2, t2); for(int i=0; i+k-1<m; i++){ if(val1[i+k-1]+val2[i]>=k){ ans=k, j1=l, j2=i; cek=true; break; } } for(int i=0; i+k-1<m; i++){ if(val3[i+k-1]+val4[i]>=k){ ans=k, j1=l, j2=m-(i+k-1)-1; cek=true; break; } } // if(ans==k){ // cout<<s1<<'\n'; // for(int i=0; i<m; i++) cout<<val3[i]<<' '; // cout<<'\n'; // for(int i=0; i<m; i++) cout<<val4[i]<<' '; // cout<<'\n'; // } } if(cek) ki=k+1; else ka=k-1; } cout<<ans<<'\n'; cout<<j1<<' '<<j2; } */ //KMP /* vector<int> f(string &s){ int n=s.size(), j=0; vector<int> v(n); for(int i=1; i<n; i++){ while(j>0 && s[i]!=s[j]) j=v[j-1]; if(s[i]==s[j]) j++; v[i]=j; } return v; } int main(){ fast(); string s, t; cin>>s>>t; string temp=t+'0'+s; auto lps=f(temp); int ans=0; for(auto i:lps) ans+=(i==t.size()); cout<<ans; }*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...