oj.uz

Submission #467728

# Submission time Handle Problem Language Result Execution time Memory
467728 2021-08-24T08:12:44 Z MohamedFaresNebili Vlak (COCI20_vlak) C++14
70 / 70
 18 ms 20428 KB 
#include <bits/stdc++.h>

using namespace std;

using ll  = long long;
using ld  = long double;
using db  = double;
using ii  = pair<int, int>;
using pl  = pair<ll, ll>;
using vi  = vector<int>;
using vl  = vector<ll>;
using vii = vector<ii>;
using vpl = vector<pl>;

#define mp make_pair
#define pb push_back
#define pp pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin() , (x).end()

const int MOD = 1000*1000*1000+7;
const long double EPS = 0.000000001;
const long long INF = 1e18;

struct node{
    bool a=false, b=false;
    node* children[26];
    node() {
        for(int l=0;l<26;l++) children[l]=nullptr;
    }
};
node* root;

void add(string s, bool t)
{
    node* next=root;
    for(auto u:s) {
        int i=u-'a';
        if(next->children[i]==nullptr) next->children[i]=new node();
        if(t) { (next->children[i])->a=true; }
        else { (next->children[i])->b=true; }
        next=(next->children[i]);
    }
    if(t) { (next->a)=true; }
    else { (next->b)=true; }
}
bool solve(bool f, node* r) {
    bool player=f; node* next=r;
    for(int l=0;l<26;l++) {
        if((next->children[l])==nullptr) continue;
        if(player) {
            if((next->children[l])->a&&(next->children[l])->b==false) return player;
            else if(solve(!f, next->children[l])==player) return player;
        }
        else {
            if((next->children[l])->b&&(next->children[l])->a==false) return player;
            else if(solve(!f, next->children[l])==player) return player;
        }
    }
    return !player;
}

int32_t main()
{
    ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
    /// freopen("closing.in", "r", stdin);
	/// freopen("closing.out", "w", stdout);
	int n; cin>>n; root=new node();
	for(int l=0;l<n;l++) {
        string s; cin>>s; add(s, 1);
	}
	int m; cin>>m;
	for(int l=0;l<m;l++) {
        string s; cin>>s; add(s, 0);
	}
	cout<<(solve(1, root)==0?"Emilija":"Nina");
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 436 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 19148 KB Output is correct
2 Correct 16 ms 17880 KB Output is correct
3 Correct 16 ms 16892 KB Output is correct
4 Correct 16 ms 18696 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19532 KB Output is correct
2 Correct 16 ms 20428 KB Output is correct
3 Correct 14 ms 18764 KB Output is correct
4 Correct 14 ms 19136 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 18380 KB Output is correct
2 Correct 15 ms 17924 KB Output is correct
3 Correct 16 ms 18508 KB Output is correct
4 Correct 16 ms 19664 KB Output is correct