Submission #448817

#	Time	Username	Problem	Language	Result	Execution time	Memory
448817		Radman_	Vlak (COCI20_vlak)	C++14	70 / 70	54 ms	56732 KiB

Main

//                  //
//     Radmanシ     //
//                 //
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<string>
#include<math.h>

using namespace std;

//#define int long long

typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef pair<int,pii> pip;
#define F first
#define S second

const int maxn=1e6+5;
int dp1[maxn],dp2[maxn];
string st[maxn];

struct Node
{
    Node *child[26];
    Node *par=nullptr;
    int height=-1,id=-1,c[3];
    vector<int> strings;
    Node()
    {
        for(int i=0;i<26;i++)
            child[i]=nullptr;
    }
};


struct Trie
{
    Node *root;
    int strType='a',cnt=1;
    Trie()
    {
        root=new Node();
        root->height=0;
        root->id=1;
    }
    void add(int num,int ty)
    {
        Node *cur=root;
        cur->c[ty]++;
        //cur->strings.push_back(num);
        for(char c : st[num])
        {
            int x=int(c)-strType;
            if(cur->child[x]==nullptr)
            {
                cur->child[x]=new Node();
                Node *next=cur->child[x];
                next->par=cur;
                next->height=cur->height+1;
                next->id=++cnt;
            }
            cur=cur->child[x];
            cur->c[ty]++;
            //cur->strings.push_back(num);
        }
    }
};

void find(Node *now)
{
    //cout<<"Now: "<<now->id<<endl;
    for(int i=0;i<26;i++)
    {
        Node *next=now->child[i];
        if(!next)
            continue;
        //cout<<"Next: "<<next->id<<endl;
        find(next);
        if(!dp2[next->id] and next->c[1])
            dp1[now->id]=1;
        if(!dp1[next->id] and next->c[2])
            dp2[now->id]=1;
    }
    return;
}

int32_t main()
{ 
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    Trie* T=new Trie;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>st[i];
        T->add(i,1);
    }
    int m;
    cin>>m;
    for(int i=n+1;i<=n+m;i++)
    {
        cin>>st[i];
        T->add(i,2);
    }
    Node *root=T->root;
    find(root);
    if(dp1[root->id])
        cout<<"Nina"<<endl;
    else
        cout<<"Emilija"<<endl;
    return 0;
}

• 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