oj.uz

Submission #1011699

# Submission time Handle Problem Language Result Execution time Memory
1011699 2024-07-01T06:42:33 Z vjudge1 Vlak (COCI20_vlak) C++
70 / 70
 17 ms 11608 KB 
#include <iostream>
#include <map>
using namespace std;

struct node
{
  map<char, node*> ch;
  bool is_prefix[3];
  bool win[3];

  void add(string &x, int player, int i=0)
  {
    is_prefix[player]=true;
    if(i>=x.size())
	return;
    char c = x[i];
    if(ch.find(c)==ch.end())
      ch[c]=new node();
    ch[c]->add(x, player, i+1);
  }

  void run_dp()
  {
    //run dp on the children
    bool lose[3]={};
    for(auto X:ch)
      {
	X.second->run_dp();
	if(!X.second->win[1])
	  lose[1]=true;
	if(!X.second->win[2])
	  lose[2]=true;
      }


    win[1]=is_prefix[1] and lose[2];
    win[2]=is_prefix[2] and lose[1];
	
  }
  
};

node *root;

int main()
{
  root = new node();
  int n;
  cin>>n;
  while(n--)
    {
      string x;
      cin>>x;
      root->add(x, 1);
    }
  cin>>n;
  while(n--)
    {
      string x;
      cin>>x;
      root->add(x, 2);
    }

  root->run_dp();

  if(root->win[1])
    cout<<"Nina"<<endl;
  else
    cout<<"Emilija"<<endl;
  
  return 0;
}

Compilation message

Main.cpp: In member function 'void node::add(std::string&, int, int)':
Main.cpp:14:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     if(i>=x.size())
      |        ~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 10844 KB Output is correct
2 Correct 16 ms 10204 KB Output is correct
3 Correct 17 ms 9820 KB Output is correct
4 Correct 17 ms 10696 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 11096 KB Output is correct
2 Correct 13 ms 11608 KB Output is correct
3 Correct 14 ms 10884 KB Output is correct
4 Correct 12 ms 10840 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 10584 KB Output is correct
2 Correct 16 ms 10332 KB Output is correct
3 Correct 16 ms 10588 KB Output is correct
4 Correct 15 ms 11384 KB Output is correct