# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
401419 |
2021-05-10T07:59:29 Z |
zipdang04 |
Vlak (COCI20_vlak) |
C++14 |
|
101 ms |
114372 KB |
#include <bits/stdc++.h>
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
*/
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef map<int, int> mii;
typedef unordered_map<int, int> umii;
typedef map<ll, ll> mll;
typedef unordered_map<ll, ll> umll;
/*
struct Node
{
int node, len;
Node() {node = len = 0;}
Node(int node, int len) {this -> node = node, this -> len = len;}
};
typedef vector<Node> vg;
*/
#define MAX 1000001
#define MOD 1000000007
#define fi first
#define se second
#define pf push_front
#define pb push_back
#define FOR(type, i, a, b) for(type i = (a); i <= (b); i++)
#define FORR(type, i, b, a) for(type i = (b); i >= (a); i--)
#define testBit(n, bit) (((n) >> (bit)) & 1)
#define flipBit(n, bit) ((n) ^ (1ll << (bit)))
#define cntBit(n) __builtin_popcount(n)
#define cntBitll(n) __builtin_popcountll(n)
#define randomize mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
int n, m;
struct Node{
int lvl = 0, cnt[2] = {};
int child[26] = {};
Node(){
lvl = cnt[0] = cnt[1] = 0;
FOR(int, i, 0, 25) child[i] = -1;
}
};
Node trie[MAX]; int len = 0;
const int root = 0;
void add(string s, int type){
int node = root;
trie[node].cnt[type]++;
int lvl = 0;
for (char c: s){
int pos = c - 'a';
if (trie[node].child[pos] == -1)
trie[node].child[pos] = ++len;
node = trie[node].child[pos];
trie[node].lvl = ++lvl;
trie[node].cnt[type]++;
}
}
int f[MAX];
int dp(int node){
if (f[node] != -1) return f[node];
Node curr = trie[node];
int turn = curr.lvl & 1;
f[node] = 0;
if (!curr.cnt[turn]) return 0;
FOR(int, choice, 0, 25){
int childPos = curr.child[choice];
if (childPos == -1) continue;
Node child = trie[childPos];
if (dp(childPos) == 0) f[node] = 1;
}
return f[node];
}
main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n; FOR(int, i, 1, n) {string s; cin >> s; add(s, 0);}
cin >> m; FOR(int, i, 1, m) {string s; cin >> s; add(s, 1);}
FOR(int, i, 0, len) f[i] = -1;
cout << (dp(root) ? "Nina" : "Emilija");
}
Compilation message
Main.cpp: In function 'int dp(int)':
Main.cpp:89:8: warning: variable 'child' set but not used [-Wunused-but-set-variable]
89 | Node child = trie[childPos];
| ^~~~~
Main.cpp: At global scope:
Main.cpp:96:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
96 | main()
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
113732 KB |
Output is correct |
2 |
Correct |
80 ms |
113804 KB |
Output is correct |
3 |
Correct |
80 ms |
113696 KB |
Output is correct |
4 |
Correct |
80 ms |
113796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
113800 KB |
Output is correct |
2 |
Correct |
79 ms |
113812 KB |
Output is correct |
3 |
Correct |
88 ms |
113784 KB |
Output is correct |
4 |
Correct |
79 ms |
113740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
113796 KB |
Output is correct |
2 |
Correct |
79 ms |
113760 KB |
Output is correct |
3 |
Correct |
79 ms |
113780 KB |
Output is correct |
4 |
Correct |
82 ms |
113812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
113780 KB |
Output is correct |
2 |
Correct |
79 ms |
113724 KB |
Output is correct |
3 |
Correct |
83 ms |
113776 KB |
Output is correct |
4 |
Correct |
79 ms |
113732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
95 ms |
114336 KB |
Output is correct |
2 |
Correct |
101 ms |
114304 KB |
Output is correct |
3 |
Correct |
88 ms |
114280 KB |
Output is correct |
4 |
Correct |
85 ms |
114252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
83 ms |
114280 KB |
Output is correct |
2 |
Correct |
83 ms |
114372 KB |
Output is correct |
3 |
Correct |
88 ms |
114268 KB |
Output is correct |
4 |
Correct |
88 ms |
114284 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
80 ms |
114284 KB |
Output is correct |
2 |
Correct |
98 ms |
114216 KB |
Output is correct |
3 |
Correct |
85 ms |
114248 KB |
Output is correct |
4 |
Correct |
86 ms |
114288 KB |
Output is correct |