USACO 2019 US Open Contest Bronze Division - Cow Evolution

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

This code is based on the solution described on USACO Guide

Source codes

The source code in C++ can be seen below.

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

int main()
{
    ifstream cin("evolution.in");
    ofstream cout("evolution.out");

    int n;
    cin >> n;

    vector<set<string> > cows;
    set<string> all_char_set;
    for (int c = 0; c < n; c++)
        {
            int char_num;
            cin >> char_num;
            set<string> curr_cow;
            for (int i = 0; i < char_num; i++)
                {
                    string characteristic;
                    cin >> characteristic;
                    curr_cow.insert (characteristic);
                }
            all_char_set.insert (curr_cow.begin (), curr_cow.end ());
            cows.push_back (curr_cow);
        }

    vector<string> all_chars (all_char_set.begin (), all_char_set.end ());

    // Iterate over every pair of characteristics and check if the tree is
    // evolutionarily proper relative to that pair
    for (int a = 0; a < all_chars.size (); a++)
    {
        for (int b = a + 1; b < all_chars.size (); b++)
        {
            bool both = false, only_a = false, only_b = false;
            for (const set<string> &c : cows)
            {
                bool has_a = c.count (all_chars[a]);
                bool has_b = c.count (all_chars[b]);

                if (has_a && has_b)
                {
                    both = true;
                }
                else 
                    if (has_a && !has_b)
                    {
                        only_a = true;
                    }
                    else 
                        if (!has_a && has_b)
                        {
                            only_b = true;
                        }
            }

            /*
             * If we find a cow which has the characteristic a,
             * another cow which has the characteristic b, and
             * another cow with both characteristics a and b, then
             * the tree isn't evolutionarily proper.
             */
            if (only_a && only_b && both)
            {
                cout << "no" << '\n';
                return 0;
            }
        }
    }

    cout << "yes" << '\n';
}