oj.uz

Submission #441997

# Submission time Handle Problem Language Result Execution time Memory
441997 2021-07-06T16:56:50 Z huukhang Vlak (COCI20_vlak) C++11
70 / 70
 19 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;
};

int dp[200005] = {0};
struct trie {
	int n;
	node t[200005];

	trie() : n(0) {
		memset(t[0].child, -1, sizeof(t[0].child));
		t[0].fin = 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 p = 0;
		for (int i = 0; i < s.size(); ++i) {
			if (t[p].child[s[i] - 'a'] == -1) {
				init(++n);
				t[p].child[s[i] - 'a'] = n;
			}
			p = t[p].child[s[i] - 'a'];
		}
		t[p].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;
		}
	}

	int res(const string &s) {
		int p = 0;
		for (int i = 0; i < s.size(); ++i) p = t[p].child[s[i] - 'a'];
		return dp[p];
	}
} 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:55:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for (int i = 0; i < s.size(); ++i) {
      |                   ~~^~~~~~~~~~
Main.cpp: In member function 'int trie::res(const string&)':
Main.cpp:86:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   for (int i = 0; i < s.size(); ++i) p = t[p].child[s[i] - 'a'];
      |                   ~~^~~~~~~~~~

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 404 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 460 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 332 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 19 ms 9804 KB Output is correct
2 Correct 19 ms 9248 KB Output is correct
3 Correct 17 ms 8760 KB Output is correct
4 Correct 19 ms 9616 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 10060 KB Output is correct
2 Correct 17 ms 10444 KB Output is correct
3 Correct 16 ms 9676 KB Output is correct
4 Correct 17 ms 9804 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 9532 KB Output is correct
2 Correct 16 ms 9296 KB Output is correct
3 Correct 17 ms 9540 KB Output is correct
4 Correct 19 ms 10060 KB Output is correct