oj.uz

Submission #448817

# Submission time Handle Problem Language Result Execution time Memory
448817 2021-08-01T20:17:30 Z Radman_ Vlak (COCI20_vlak) C++14
70 / 70
 54 ms 56732 KB 
//                  //
//     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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31948 KB Output is correct
2 Correct 16 ms 31956 KB Output is correct
3 Correct 16 ms 31952 KB Output is correct
4 Correct 16 ms 31920 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 31888 KB Output is correct
2 Correct 17 ms 31888 KB Output is correct
3 Correct 17 ms 31920 KB Output is correct
4 Correct 16 ms 31948 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 31820 KB Output is correct
2 Correct 16 ms 31820 KB Output is correct
3 Correct 16 ms 31820 KB Output is correct
4 Correct 18 ms 31884 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31820 KB Output is correct
2 Correct 17 ms 31940 KB Output is correct
3 Correct 17 ms 31892 KB Output is correct
4 Correct 16 ms 31792 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 55428 KB Output is correct
2 Correct 42 ms 53812 KB Output is correct
3 Correct 42 ms 52536 KB Output is correct
4 Correct 44 ms 54728 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 55748 KB Output is correct
2 Correct 41 ms 56732 KB Output is correct
3 Correct 39 ms 54840 KB Output is correct
4 Correct 41 ms 55212 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 54492 KB Output is correct
2 Correct 46 ms 53872 KB Output is correct
3 Correct 42 ms 54480 KB Output is correct
4 Correct 44 ms 55876 KB Output is correct