oj.uz

Submission #711516

# Submission time Handle Problem Language Result Execution time Memory
711516 2023-03-17T06:49:59 Z badont Vlak (COCI20_vlak) C++17
70 / 70
 26 ms 14720 KB 
#include<bits/stdc++.h>
using namespace std;

void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }

#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif

using ll = long long;
using ld = long double;
using pii = pair<ll,ll>;

#define FOR(i, n) for(int i = 1; i<=n; i++)
#define F0R(i, n) for(int i = 0; i<n; i++)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second

template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
	cout << "["; 
	for (auto it = v.begin(); it != v.end();) {
		cout << *it;
		if (++it != v.end()) cout << ", ";
	}
	return cout << "]";
}

//var 
ll T;
struct Node {
	ll sub_a, sub_b;
	vector<int> e;
	array<int, 2> dp;

	Node() : e(26, -1), sub_a(0), sub_b(0), dp({0, 0}) {};
};

vector<Node> a = {Node{}};

void solve() {
	ll n, m;
	cin >> n; 

	while (n--) {
		string s; cin >> s;
		int c = 0;
		vector<int> order;
		for (auto u : s) {
			order.pb(c);
			if (a[c].e[u - 'a'] == -1) {
				a[c].e[u - 'a'] = (int)a.size();
				c = (int)a.size();
				a.pb(Node{});
			} else {
				c = a[c].e[u - 'a'];
			}
		}
		order.pb(c);
		for (auto u : order) a[u].sub_a++;
	}

	cin >> m;
	while (m--) {
		string s; cin >> s;
		int c = 0;
		vector<int> order;
		for (auto u : s) {
			order.pb(c);
			if (a[c].e[u - 'a'] == -1) {
				a[c].e[u - 'a'] = (int)a.size();
				c = (int)a.size();
				a.pb(Node{});
			} else {
				c = a[c].e[u - 'a'];
			}
		}
		order.pb(c);
		for (auto u : order) a[u].sub_b++;
	}

	auto dfs = [&](auto dfs, int g, int player) -> int {

		vector<int> transitions;

		for (int i = 0; i < 26; i++) {
			int u = a[g].e[i];
			if (u != -1) {
				if (player == 0 and a[u].sub_a)
					transitions.pb(dfs(dfs, u, player ^ 1));
				if (player == 1 and a[u].sub_b)
					transitions.pb(dfs(dfs, u, player ^ 1));
			} 
		}

		if (transitions.empty()) {
			return (player ^ 1);
			assert(false);;
		}

		for (auto u : transitions) if (u == player)
			return player;

		return (player ^ 1);
	};

	auto ans = dfs(dfs, 0, 0);
	cout << (ans == 0 ? "Nina" : "Emilija") << "\n";
}

int main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(0);

	T = 1;
	//cin >> T;
	FOR(t, T)
		solve();

	cout.flush();
	return 0;
}

Compilation message

Main.cpp: In constructor 'Node::Node()':
Main.cpp:42:14: warning: 'Node::e' will be initialized after [-Wreorder]
   42 |  vector<int> e;
      |              ^
Main.cpp:41:5: warning:   'll Node::sub_a' [-Wreorder]
   41 |  ll sub_a, sub_b;
      |     ^~~~~
Main.cpp:45:2: warning:   when initialized here [-Wreorder]
   45 |  Node() : e(26, -1), sub_a(0), sub_b(0), dp({0, 0}) {};
      |  ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 472 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 1 ms 464 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 13828 KB Output is correct
2 Correct 23 ms 13884 KB Output is correct
3 Correct 24 ms 13808 KB Output is correct
4 Correct 23 ms 13828 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 14176 KB Output is correct
2 Correct 18 ms 14720 KB Output is correct
3 Correct 17 ms 13820 KB Output is correct
4 Correct 19 ms 13784 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 13820 KB Output is correct
2 Correct 25 ms 13844 KB Output is correct
3 Correct 25 ms 13788 KB Output is correct
4 Correct 26 ms 14208 KB Output is correct