Submission #489282

#	Time	Username	Problem	Language	Result	Execution time	Memory
489282		inksamurai	Vlak (COCI20_vlak)	C++17	70 / 70	74 ms	71652 KiB

Main

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define crep(i,x,n) for(int i=x;i<n;i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _3HIYw7x ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
using pii=pair<int,int>;
using vi=vector<int>;

const int _n=2e5+1;

struct trie{
	vec(vi) to;
	int cnt=0;
	void init(int n){
		to=vec(vi)(n,vi(27,-1));
		cnt=0;
	}
};

int main(){
_3HIYw7x;
	int n;
	cin>>n;
	vec(string) a(n);
	rep(i,n){
		cin>>a[i];
	}
	int m;
	cin>>m;
	vec(string) b(m);
	rep(i,m){
		cin>>b[i];
	}
	trie _a;
	_a.init(_n);
	rep(i,n){
		int root=0;
		rep(j,sz(a[i])){
			int x=a[i][j]-'a';
			if(_a.to[root][x]==-1){
				_a.cnt++;
				_a.to[root][x]=_a.cnt;
			}
			root=_a.to[root][x];
		}
	}
	trie _b;
	_b.init(_n);
	rep(i,m){
		int root=0;
		rep(j,sz(b[i])){
			int x=b[i][j]-'a';
			if(_b.to[root][x]==-1){
				_b.cnt++;
				_b.to[root][x]=_b.cnt;
			}
			root=_b.to[root][x];
		}		
	}
	vec(vi) dp(_n,vi(2,-1));
	auto dfs=[&](auto self,int v,int v1,int t)->int{
		if(dp[v][t]!=-1) return dp[v][t];
		int pok=0;
		rep(ch,26){
			if(t==0){
				if(_a.to[v][ch]!=-1){
					if(_b.to[v1][ch]==-1){
						pok=1;
						break;
					}
					pok=pok or !self(self,_a.to[v][ch],_b.to[v1][ch],1);
				}
			}else{
				if(_b.to[v1][ch]!=-1){
					if(_a.to[v][ch]==-1){
						pok=1;
						break;
					}
					pok=pok or !self(self,_a.to[v][ch],_b.to[v1][ch],0);
				}
			}
		}
		return dp[v][t]=pok;
	};
	dfs(dfs,0,0,0);
	cout<<(dp[0][0]?"Nina":"Emilija")<<"\n";
//	
	return 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