제출 #1153922

#제출 시각아이디문제언어결과실행 시간메모리
1153922i271828Vlak (COCI20_vlak)C++20
70 / 70
31 ms46004 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;

bool calc(int p1,int p2,bool cur){
	bool oth=!cur;
	for (auto pr:t[cur]->c[p1]){
		auto ch=pr.first;
		if (!t[oth]->get(p2,ch)) return true;
		
		auto x=pr.second;
		auto othx=t[oth]->c[p2][ch];
		if (!calc(othx,x,oth)) return true;
	}
	return false;
}

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 (calc(0,0,0)) cout<<"Nina";
	else cout<<"Emilija";
}
#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...