oj.uz

Submission #475786

# Submission time Handle Problem Language Result Execution time Memory
475786 2021-09-24T04:41:10 Z huukhang Vlak (COCI20_vlak) C++11
70 / 70
 20 ms 10444 KB 
/*
						   Khangnh's code
 
“You can either experience the pain of discipline or the pain of regret. 
						The choice is yours.”
*/
 
// - Only when necessary :d
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx,avx2,fma")
 
#include <bits/stdc++.h>
using namespace std;
 
#define fileopen(a, b) freopen(((string)a + ".inp").c_str(), "r", stdin); freopen(((string)b + ".out").c_str(), "w", stdout);
 
#define ll long long
// #define int long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
typedef pair<int, int> pii;
 
const ll mod = 1e9 + 7;
const ll inf = 1e9 + 7;
const double eps = 1e-9;
 
struct node {
	int child[26];
	int fin;	// In this problem, fin is a variable that determines whether we can reach a string that belongs to Nina, Emilija or not (taking into account the fact that Nina chooses first, then Emilija, then Nina again, etc)
};
 
int dp[200005] = {0};
struct trie {
	int n;
	node t[200005];
 
	trie() : n(0) {init(0);}
 
	void init(int u) {
		memset(t[u].child, -1, sizeof(t[u].child));
		t[u].fin = 0;
	}
 
	void push(const string &s, int k) {
		int u = 0;
		for (int i = 0; i < s.size(); ++i) {
			if (t[u].child[s[i] - 'a'] == -1) {
				init(++n);
				t[u].child[s[i] - 'a'] = n;
			}
			u = t[u].child[s[i] - 'a'];
		}
		t[u].fin |= k;
	}
 
	void dfs(int u, int dep = 0) {
		dp[u] = t[u].fin;
		for (int i = 0; i < 26; ++i) {
			if (t[u].child[i] != -1) {
				dfs(t[u].child[i], dep + 1);
				dp[u] |= dp[t[u].child[i]];
			}
		}
		if (t[u].fin > 0) return;
 
		if (dep%2 == 0) {
			if ((dp[u] >> 0) & 1) dp[u] = 1;
			else dp[u] = 2;
		} else {
			if ((dp[u] >> 1) & 1) dp[u] = 2;
			else dp[u] = 1;
		}
	}
} t;
 
int n, m;
 
void solve() {
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		string s;
		cin >> s;
		t.push(s, 1);
	}
	cin >> m;
	for (int i = 1; i <= m; ++i) {
		string s;
		cin >> s;
		t.push(s, 2);
	}
 
	t.dfs(0);
	cout << ((dp[0] == 1) ? "Nina" : "Emilija");
}
 
signed main() {
	#ifdef LOCAL
		fileopen("input", "output");
		auto start = clock();
	#endif
	#ifndef LOCAL
//		fileopen("LAH", "LAH");
	#endif
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int test = 1;
//	cin >> test;
	for (int tc = 1; tc <= test; ++tc) solve();
	#ifdef LOCAL
		auto end = clock();
		cout << "\n\nExecution time : " << double(end - start)/CLOCKS_PER_SEC << "[s]";
	#endif
	return 0;
}

Compilation message

Main.cpp: In member function 'void trie::push(const string&, int)':
Main.cpp:52:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for (int i = 0; i < s.size(); ++i) {
      |                   ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 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 332 KB Output is correct

Subtask #2
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 452 KB Output is correct
4 Correct 1 ms 332 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 9860 KB Output is correct
2 Correct 17 ms 9152 KB Output is correct
3 Correct 16 ms 8760 KB Output is correct
4 Correct 18 ms 9616 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 10004 KB Output is correct
2 Correct 18 ms 10444 KB Output is correct
3 Correct 16 ms 9684 KB Output is correct
4 Correct 16 ms 9832 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 9420 KB Output is correct
2 Correct 18 ms 9292 KB Output is correct
3 Correct 16 ms 9420 KB Output is correct
4 Correct 16 ms 10060 KB Output is correct