题目

题目链接

题解

STL。


保存关系时,我们让儿子指向父亲,而不是父亲指向儿子,一个儿子有一个父亲,但一个父亲有多个儿子。查询时,两个人不停地向上找父亲,如果存在一个人的五代内的祖先与另一个人的某个祖先是同一个人,则false,如果没找到,则true。


最开始我使用邻接表,再两次bfs,第一次bfs标记第一个人五代内的祖先,第二次bfs找第二个人五代内的祖先是否被标记,存在被标记说明不可行,否则可行。

判断方式已经出现了问题,题目要求所谓“五代以内无公共祖先”是指两人的公共祖先(如果存在的话)必须比任何一方的曾祖父辈分高。,这句话的含义是可能存在二者的公共祖先是a的曾曾曾……曾祖父,是b的祖父,这样一来虽然祖先不是a的五代内的祖先,但却是b五代内的祖先,所以这种情况也要输出yes。如果单纯使用上面的bfs是不能实现的。

代码

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

const int N = 1e6+10;

int n, k;

struct node {
	bool sex;
	string fa = "";
};

map<string, node> peo;

string getlastname (string s) {
	char ch = s.back();
	if (ch == 'f' || ch == 'm') return "";
	return s.substr (0, s.size() - (ch == 'n' ? 4 : 7));
}

bool check (string a, string b) {
	int i = 1;
	for (string x = a;x.size();x = peo[x].fa, i ++) {
		int j = 1;
		for (string y = b;y.size();y = peo[y].fa, j ++) {
			if (i >= 5 && j >= 5) break;
			if (x == y) return false;
		}
	}
	return true;
}

int main()
{
	cin >> n;
	for (int i = 0;i < n;i ++) {
		string fn, ln;
		cin >> fn >> ln;
		peo[fn].sex = (ln.back() == 'm' || ln.back() == 'n');
		peo[fn].fa = getlastname(ln);
//		cout << peo[fn].sex << ' ' << peo[fn].fa << endl;
	}	
	cin >> k;
	while (k --) {
		string afn, bfn, aln, bln;
		cin >> afn >> aln >> bfn >> bln;
		if (peo.find (afn) == peo.end() || peo.find (bfn) == peo.end()) puts ("NA");
		else if (peo[afn].sex == peo[bfn].sex) puts ("Whatever");
		else if (check (afn, bfn)) puts ("Yes");
		else puts ("No");
	}
	return 0;
}