oj.uz

Submission #1022582

# Submission time Handle Problem Language Result Execution time Memory
1022582 2024-07-13T18:50:47 Z subrat0018 Vlak (COCI20_vlak) C++17
70 / 70
 35 ms 29264 KB 
#include <bits/stdc++.h>
using namespace std;
#define nline "\n"
using uint = unsigned int;
using ull = unsigned long long;
using ll = long long;
const ll M = 1e9 + 7;
const ll M2 = 998244353;
const ll INF = 2e18;
const ll N = 3e5 + 10;
const double Degree = 57.2958;

/***************************************Debug***********************************************************/
/***************************************Debug***********************************************************/
/***************************************Debug***********************************************************/


#ifndef ONLINE_JUDGE
#define debug(x) cerr<< #x << " ";_print(x);cerr<<nline;
#else
#define debug(x)
#endif
void _print(int x) {cerr << x;}
void _print(bool x) {cerr << x;}
void _print(char x) {cerr << x;}
void _print(string x) {cerr << x;}
void _print(ll x) {cerr << x;}
void _print(ull x) {cerr << x;}
void _print(float x) {cerr << x;}
void _print(double x) {cerr << x;}
template<class T>void _print(set<T> v);
template<class T>void _print(vector<T> v);
template<class T>void _print(multiset<T> v);
template<class T>void _print(unordered_set<T> v);
template<class T, class V>void _print(map<T, V> v);
template<class T, class V>void _print(unordered_map<T, V> v);
template<class T>void _print(vector<vector<T>> v);
template<class T>void _print(stack<T> v);
template<class T>void _print(queue<T> v);
template<class T, class V>void _print(pair<T, V> p);
template<class T>void _print(queue<T> v) {cerr << "[ "; while (!v.empty()) {_print(v.front()); cerr << " "; v.pop();} cerr << " ]";}
template<class T>void _print(stack<T> v) {cerr << "[ "; while (!v.empty()) {_print(v.top()); cerr << " "; v.pop();} cerr << " ]";}
template<class T, class V>void _print(pair<T, V> p) {_print(p.first); cerr << " "; _print(p.second); cerr << nline;}
template<class T>void _print(set<T> v) {cerr << "[ "; for (auto &i : v) {_print(i); cerr << " ";} cerr << "]";}
template<class T>void _print(vector<T> v) {cerr << "[ "; for (auto &i : v) {_print(i); cerr << " ";} cerr << "]";}
template<class T>void _print(multiset<T> v) {cerr << "[ "; for (auto &i : v) {_print(i); cerr << " ";} cerr << "]";}
template<class T>void _print(unordered_set<T> v) {cerr << "[ "; for (auto &i : v) {_print(i); cerr << " ";} cerr << "]";}
template<class T, class V>void _print(map<T, V> v) {cerr << "[ "; for (auto &i : v) {_print(i.first); cerr << " "; _print(i.second); cerr << "\n";} cerr << "]";}
template<class T, class V>void _print(unordered_map<T, V> v) {cerr << "[ "; for (auto &i : v) {_print(i.first); cerr << " "; _print(i.second); cerr << "\n";} cerr << "]";}
template<class T>void _print(vector<vector<T>> v) {cerr << "[ "; for (auto &i : v) {_print(i); cerr << nline;} cerr << "]";}



/************************************************************************************************************/
/************************************************************************************************************/
/************************************************************************************************************/


class Node{
public:
    vector<Node*> links;  
    Node(){
        links.resize(26, nullptr);
    }  
};
class Trie{
public:
    Node *root;
    Trie(){
        root = new Node();
    }
    void insert(string &s){
        Node *node = root;
        for(auto &val: s){
            if(!node->links[val - 'a']){
                node->links[val - 'a'] = new Node();
            }
            node = node->links[val - 'a'];
        }
    }
};
map<Node *, Node *> mp;
void dfs(Node *n, Node *e){
    mp[n] = e;
    for(int i=0;i<26;i++){
        if(n->links[i]){
            dfs(n->links[i], (e?e->links[i]:nullptr));
        }
    }
}
map<pair<Node *, bool>, bool> dp;
bool func(Node *n, bool ok){
    if(!n)
        return false;
    Node *e = mp[n];
    if(!e)
        return true;
    if(dp.find({n, ok}) != dp.end())return dp[{n, ok}];
    if(ok){
        bool ans = false;
        for(int i=0;i<26;i++){
            if(n->links[i]){
                ans |= func(n->links[i], !ok);
            }
        }
        return ans;
    }
    bool ans = true;
    for(int i=0;i<26;i++){
        if(e->links[i]){
            ans &= func(n->links[i], !ok);
        }
    }
    return dp[{n, ok}] = ans;
}
void solve()
{
    int n;cin>>n;
    Trie Nina, Emilija;
    for(int i=0;i<n;i++){
        string s;cin>>s;
        Nina.insert(s);
    }
    int m;cin>>m;
    for(int i=0;i<m;i++){
        string s;cin>>s;
        Emilija.insert(s);
    }
    dfs(Nina.root, Emilija.root);
    cout<<(func(Nina.root, true)?"Nina":"Emilija")<<nline;
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("debug.txt", "w", stderr);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    // cin>>t;
    // prec();
    for (int i = 1; i <= t; i++)
    {
        // cout<<"Case "<<i<<": ";
        solve();
    }

    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:135:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |     freopen("debug.txt", "w", stderr);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 27480 KB Output is correct
2 Correct 27 ms 25580 KB Output is correct
3 Correct 26 ms 24408 KB Output is correct
4 Correct 28 ms 26728 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 27732 KB Output is correct
2 Correct 27 ms 29264 KB Output is correct
3 Correct 25 ms 26964 KB Output is correct
4 Correct 28 ms 27228 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 26448 KB Output is correct
2 Correct 29 ms 25684 KB Output is correct
3 Correct 29 ms 26208 KB Output is correct
4 Correct 33 ms 27984 KB Output is correct