Submission #1096669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096669		lenron	Vlak (COCI20_vlak)	C++17	40 / 70	62 ms	103772 KiB

Main

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

vector<vector<ll>> trie(400040,vector<ll>(26,0));
vector<int> color(400040,0);
vector<int> res(400040,0);
vector<ll> depth(400040,0);
ll node_c=0;
void insert(string s,int x){
       ll node =0;
       ll d=depth[node];
       for(auto c:s){
         if(trie[node][c-'a']==0){node_c++;trie[node][c-'a']=node_c;}
         node=trie[node][c-'a'];
         depth[node]=d+1;
         d++;
         color[node]+=x;
       }

}

void dfs(ll u){
    //cout<<"*"<<u<<endl;
    if(color[u]==1){
        res[u]=1;return;
    }
    if(color[u]==-1){
        res[u]=2;return;
    }
    bool flag=false;
    set<int> s;
    for(int i=0;i<26;i++){
        if(trie[u][i]==0){continue;}
        flag=true;
        dfs(trie[u][i]);
       s.insert(res[trie[u][i]]);
       res[u]=res[trie[u][i]];
    }

    if(!flag){
        if(depth[u]%2){res[u]=1;return;}
        else{res[u]=2;return;}
    }

   if(depth[u]%2 && s.find(2)!=s.end()){res[u]=2;return;}
   if(depth[u]%2==0 && s.find(1)!=s.end()){res[u]=1;return;}



}

void solve(){
    ll a;cin>>a;
    for(ll i=0;i<a;i++){
        string s;cin>>s;
        insert(s,1);
    }
    ll b;cin>>b;
    for(ll i=0;i<b;i++){
        string s;cin>>s;
        insert(s,-1);
    }
    dfs(0);
    if(res[0]==1){cout<<"Nina"<<endl;}
    else{cout<<"Emilija"<<endl;}
}

int main(){
	solve();
}

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