团体程序设计天梯赛 L2-030 冰岛人 (25分)

题目链接：

L2-030 冰岛人 (25分)

思路：

此题细心处理字符串，存储相应的信息，最后寻找有无LCA，如果有检查是否超过五代；
可能map用多了…最后一个测试点提交上去有时候TLE…

代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>

using namespace std;              //最后一个测试点有时候会TLE QAQ 

unordered_map<string, int> sex;
unordered_map<string, string> fa;

inline bool check(string & a, string & b) {
	unordered_map<string, int> rcd;
	for(int i = 1; a != ""; ++i, a = fa[a]) rcd[a] = i;	
	for(int i = 1; b != ""; ++i, b = fa[b]) {
		if(rcd[b] && (rcd[b] < 5 || i < 5)) return false;
		if(rcd[b] >= 5) return true;	
	}
	return true;
}
#define len(s) s.length()
int main() {
#ifdef MyTest
	freopen("Sakura.txt", "r", stdin);
#else
	ios::sync_with_stdio(false);
	cin.tie(0);
#endif	
	int n, m;
	cin >> n;
	for(int i = 0; i < n; ++i) {
		string a, b;
		cin >> a >> b;	
		string s = a + ' ' + b;
		if(b[len(b) - 1] == 'm') sex[s = s.substr(0, len(s) - 1)] = 1;
		else if(b[len(b) - 1] == 'f') sex[s = s.substr(0, len(s) - 1)] = -1;
		else if(b.substr(len(b) - 4) == "sson") {
			sex[s = s.substr(0, len(s) - 4)] = 1;
			fa[a] = b.substr(0, len(b) - 4);
		}
		else if(b.substr(len(b) - 7) == "sdottir") {
			sex[s = s.substr(0, len(s) - 7)] = -1;
			fa[a] = b.substr(0, len(b) - 7);	
		}
	}
	for(cin >> m; m--;) {
		string a, b, c, d;
		cin >> a >> b >> c >> d;
		string x = a + ' ' + b, y = c + ' ' + d;
		if(sex[x] == 0 || sex[y] == 0) cout << "NA
";
		else if(sex[x] == sex[y]) cout << "Whatever
";
		else cout << (check(a, c) ? "Yes
" : "No
");
	}
	return 0;
}