USACO 2018 US Open Contest Bronze Division - Family Tree

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Just implement what you are told to do, be careful about cases and you are good to go, the relative small constraints help a lot here with this graph setup.

Source codes

The source codes in C++ and Python can be seen below.

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

int n;
string daughter[101], mother[101];

string find_mother(string cow) {
    for (int i = 0; i < n; i++)
        if (cow == daughter[i]) return mother[i];
    return "";
}

int is_ancestor(string cow1, string cow2) {
    int counter = 0;
    while (cow2 != "") {
        if (cow1 == cow2) return counter;
        cow2 = find_mother(cow2);
        counter++;
    }
    return -1;
}

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

    string bessie, elsie;
    cin >> n >> bessie >> elsie;
    for (int i = 0; i < n; i++) {
        cin >> mother[i] >> daughter[i];
    }

    string cow = bessie;
    int b = 0;
    while (cow != "") {
        if (is_ancestor(cow, elsie) != -1) {
            break;
        }
        cow = find_mother(cow);
        b++;
    }
    if (cow == "") {
        cout << "NOT RELATED\n";
        return 0;
    }
    int a = is_ancestor(cow, elsie);
    if (a == 1 && b == 1) {
        cout << "SIBLINGS\n";
    }
    else 
        if (a > 1 && b > 1) {
            cout << "COUSINS\n";
        }
        else {
            if (a > b) {
                swap(elsie, bessie);
                swap(a, b);
            }
            cout << elsie << " is the ";
            for (int i = 0; i < b - 2; i++) {
                cout << "great-";
            }
            if (b > 1 && a == 0) {
                cout << "grand-";
            }
            if (a == 0) {
                cout << "mother";
            }
            else {
                cout << "aunt";
            }
            cout << " of " << bessie << '\n';
        }
    return 0;
}

def find_mother(cow):
    for i in range(n):
        if cow == daughter[i]:
            return mother[i]
    return ""

def is_ancestor(cow1, cow2):
    counter = 0
    while cow2 != "":
        if cow1 == cow2:
            return counter
        cow2 = find_mother(cow2)
        counter += 1
    return -1

with open("family.in", "r") as fin:
    parts = fin.read().split()
n = int(parts[0])
bessie = parts[1]
elsie = parts[2]

mother = ["" for _ in range(n)]
daughter = ["" for _ in range(n)]
idx = 3
for i in range(n):
    mother[i] = parts[idx]
    daughter[i] = parts[idx+1]
    idx += 2

cow = bessie
b = 0
while cow != "":
    if is_ancestor(cow, elsie) != -1:
        break
    cow = find_mother(cow)
    b += 1

if cow == "":
    with open("family.out", "w") as fout:
        fout.write("NOT RELATED\n")
    exit(0)

a = is_ancestor(cow, elsie)
with open("family.out", "w") as fout:
    if a == 1 and b == 1:
        fout.write("SIBLINGS\n")
    elif a > 1 and b > 1:
        fout.write("COUSINS\n")
    else:
        if a > b:
            elsie, bessie = bessie, elsie
            a, b = b, a
        result = elsie + " is the "
        result += "great-" * (b - 2)
        if b > 1 and a == 0:
            result += "grand-"
        if a == 0:
            result += "mother"
        else:
            result += "aunt"
        result += " of " + bessie + "\n"
        fout.write(result)