Submission #1133663

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133663		WH8	Vlak (COCI20_vlak)	C++20	70 / 70	28 ms	20292 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define iloop(x, n) for (long long i = x; i < n; ++i)
#define jloop(x, n) for (long long j = x; j < n; ++j)
#define kloop(x, n) for (long long k = x; k < n; ++k)
#define dloop(x, n) for (long long d = x; d >= n; --d)
#define ll long long
#define pll pair<long long, long long>
#define pii pair<int, int>
#define iii tuple<int, int, int>
#define vi vector<int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define int long long
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define dg(x) cout << #x << ": " << x << endl
#define all(x) x.begin(), x.end()
#define flag cout << "HERE" << endl;
#define FASTIO               \
    ios::sync_with_stdio(false); \
	cin.tie(0);              \
    cout.tie(0);
#define prt(x) \
    cout << "Vector " << #x << endl << ":"; \
    for (auto it : x) cout << it << " "; \
    cout << endl;
#define ppr(x) \
    cout << "Pair " << #x << endl << ":";\
    cout << x.first << " " << x.second << endl;

int x[200005][26];
int depth[200005];
int mem[200005];
int nxt = 2; // next node number (root node is 1);
void build(vector<int> & vec, int pl){ // string to add is s
	int i = 0, v = 1;
	while (i < vec.size()){
		if (x[v][vec[i]] == 0) { // if edge 's[i]' from current node v does not exist, make it
			v = x[v][vec[i]] = nxt;
			depth[nxt] = depth[v] + 1;
			i++, nxt++;
		}
		else {
			v = x[v][vec[i]]; // follow along existing edge
			i++;
		}
		if (i == vec.size() ){
			if (pl == 0) mem[v] += 1;
			else mem[v] += 2;
		}
	}
}

bool dp(int node, int pl){
	bool gotchild = false;
	//printf("node %lld, depth %lld, player %lld\n", node, depth[node], pl);
	iloop(0, 26){
		if (x[node][i] == 0) continue;
		if (!dp(x[node][i], !pl)){
			return true;
		}
		gotchild = true;
	}
	if (!gotchild) {
		if ((mem[node] & (1 << !pl)) == 0) return true;
	}
	return false;
}

signed main(){
	int a; cin >> a;
	
	iloop(0, a){
		string s;
		cin >> s;
		vector<int> v;
		jloop(0, s.size()){
			v.pb(s[j] - 'a');
		} 
		build(v, 0);
	}

	int b; cin >> b;
	iloop(0, b){
		string s;
		cin >> s;
		vector<int> v;
		jloop(0, s.size()){
			v.pb(s[j] - 'a');
		} 
		build(v, 1);
	}
	if (dp(1, 0)) cout << "Nina";
	else cout << "Emilija";
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10