제출 #855823

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
855823		GoldLight	Vlak (COCI20_vlak)	C++17	70 / 70	16 ms	22620 KiB

Main

#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;
}*/

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10