Submission #1153910

#TimeUsernameProblemLanguageResultExecution timeMemory
1153910i271828Vlak (COCI20_vlak)C++20
0 / 70
31 ms45496 KiB
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;

const int MAX=200005;

int N=2;
int M=2;
string song[2][MAX]={{"acg","beh"},{"adi","bfj"}};

struct Tree{
	map<char,int> c[MAX];
	vector<string> val={""};
	int cur=1;
	
	void add(string s){
		int p=0;
		string cs="";
		for (int i=0;i<s.size();i++){
			cs.push_back(s[i]);
			if (c[p].find(s[i])==c[p].end()){
				c[p][s[i]]=cur;
				val.push_back(cs);
				p=cur;
				cur++;
			} else p=c[p][s[i]];
		}
	}
	
	bool get(int p, char s){
		if (c[p].find(s)==c[p].end()) return false;
		else return true;
	}
};

vector<int> words[2]={{0},{0}};
vector<int> newwords[2];

Tree* t[2]={new Tree(),new Tree()};

bool cur=0;

int main(){
	cin>>N;
	for (int i=0;i<N;i++) cin>>song[0][i];
	cin>>M;
	for (int i=0;i<N;i++) cin>>song[1][i];
	
	for (int i=0;i<N;i++) t[0]->add(song[0][i]);
	for (int i=0;i<M;i++) t[1]->add(song[1][i]);
	
	bool done=false;
	while (!done){
		for (int i=0;i<words[cur].size();i++){
			int x=words[cur][i];
			bool oth=!cur;
			int othx=words[oth][i];
			
			for (auto pr:t[cur]->c[x]){
				auto ch=pr.first;
				//cout<<t[cur]->val[x]<<' '<<ch<<'\n';
				newwords[cur].push_back(t[cur]->c[x][ch]);
				if (t[oth]->get(othx,ch)){
					newwords[oth].push_back(t[oth]->c[othx][ch]);
				}else{
					//cout<<t[oth]->val[othx]<<ch<<'\n';
					done=true;
				}
			}
		}
		
		for (int l=0;l<2;l++){
			words[l].clear();
			for (int i=0;i<newwords[l].size();i++) words[l].push_back(newwords[l][i]);
			newwords[l].clear();
		}
		cur=!cur;
	}
	if (cur==0) cout<<"Emilija";
	else cout<<"Nina";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...