L2-030 冰岛人 (25 分) （最近公共祖先 思维

添加链接描述

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
unordered_map<string, int> sex;
unordered_map<string, int> id;
unordered_map<int, string> name;
struct node {
    
    string s;
};
unordered_map<string,node>arr;
int tot = 1, flag;
bool check(string a,string b)
{
    
    // cout << name[u] << "\n"; 
    int tota=0;
    while(a!=""){
    
        tota++;
        
        int totb=0;
        string p=b;
        while(p!=""){
    
            totb++;
            if(a==p&&(tota<=4||totb<=4)){
    
                return 0;
            }
            if(tota>4&&totb>4)return 1;
            p=arr[p].s;
        }
        a=arr[a].s;

    }
    return 1;
}
int main()
{
    
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
    
        string a, b, A, B;
        cin >> a >> b;
        if (id[a] == 0)
        {
    
            id[a] = tot;
            name[tot++] = a;
        }

        if (b.back() == 'm')
        {
    

            B = b.substr(0, b.size() - 1), sex[a] = 1;
            
        }
        else if (b.back() == 'f')
            sex[a] = 2, B = b.substr(0, b.size() - 1);
        else if (b.back() == 'n')
        {
    
            sex[a] = 1;
            B = b.substr(0, b.size() - 4);
            if (id[B] == 0)
            {
    
                id[B] = tot;
                name[tot++] = B;
            }
            arr[a]={
    B};
            // cout<<a<<" "<<id[a]<<" "<<id[B]<<"\n";
            // v[id[a]].push_back(id[B]);
        }
        else if (b.back() == 'r')
        {
    
            sex[a] = 2;
            B = b.substr(0, b.size() - 7);
            if (id[B] == 0)
            {
    
                id[B] = tot;
                name[tot++] = B;
            }
            arr[a]={
    B};
            // cout<<a<<" "<<id[a]<<" "<<id[B]<<"\n";
            // v[id[a]].push_back(id[B]);
        }
        // v[id[a]].push_back(id[B]);
    }
    int q;
    cin >> q;
    while (q--)
    {
    
        string a1, b1, a2, b2;
        cin >> a1 >> b1 >> a2 >> b2;
        if (id[a1] == 0 || id[a2] == 0)
        {
    
            cout << "NA\n";
            continue;
        }
        if (sex[a1] == sex[a2])
        {
    
            cout << "Whatever\n";
            continue;
        }
       
        
        flag = 0;
        flag=check(a1, a2);
        
        if (!flag)
        {
    
            cout << "No\n";
        }
        else
            cout << "Yes\n";
    }
    return 0;
}