Submission #530785

#	Time	Username	Problem	Language	Result	Execution time	Memory
530785		Pietra	Vlak (COCI20_vlak)	C++14	70 / 70	21 ms	18308 KiB

Main

#include<bits/stdc++.h>
using namespace std ; 

const int maxn = 2e5 + 5 ; 

int n, ct = 1, trie[2][maxn][32], lvl[maxn], fim[maxn], dp[maxn], ctt[2][maxn] ; 

void add(int type, string s){

	int rt = 0, nivel = 0 ; 

	for(int i = 0 ; i < (int)s.size() ; i++){
		if(type == 1 && trie[0][rt][s[i]-'a']) trie[1][rt][s[i]-'a'] = trie[0][rt][s[i]-'a'] ;  
		else if(trie[type][rt][s[i]-'a'] == 0) trie[type][rt][s[i]-'a'] = ct++ ;
		// cout << trie[type][rt][s[i]-'a'] << " " << rt << " " << s[i] - 'a' << "\n" ; 
		ctt[type][rt]++ ;
		rt = trie[type][rt][s[i]-'a'] ; 
	}

	fim[rt] = 1 ; 

}

void view(int type, int node){

	if(ctt[type][node] == 0) return ; 

	for(int i = 0 ; i < 26 ; i++){
		if(trie[type][node][i] == 0) continue ; 
		cout << trie[type][node][i] << " " << i << "\n" ; 
	}

	for(int i = 0 ; i < 26 ; i++){
		if(trie[type][node][i] == 0) continue ; 
		view(type, trie[type][node][i]) ;
	}

}

int dp_solve(int node, int turn){

	if(dp[node] != -1) return dp[node] ; 

	if(ctt[turn][node] == 0) return dp[node] = 0 ; 

	dp[node] = 0 ; 

	for(int i = 0 ; i < 26 ; i++){
		if(trie[turn][node][i] == 0) continue ; 
		if(dp_solve(trie[turn][node][i], !turn) == 0) dp[node] = 1 ; 
	}

	return dp[node] ; 

}

int32_t main(){

	string s ; 
	cin >> n ; 

	for(int i = 1 ; i <= n ; i++){
		cin >> s ; 
		add(0, s) ; 
	}  

	// view(0, 0) ; 

	cin >> n ; 

	for(int i = 1 ; i <= n ; i++){
		cin >> s ; 
		add(1, s) ; 
	}
	
	// view(1, 0) ; 

	memset(dp, -1, sizeof dp) ; 

	cout << (dp_solve(0, 0) ? "Nina\n" : "Emilija\n") ; 

}

Compilation message (stderr)

Main.cpp: In function 'void add(int, std::string)':
Main.cpp:10:14: warning: unused variable 'nivel' [-Wunused-variable]
   10 |  int rt = 0, nivel = 0 ;
      |              ^~~~~

• 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