L2-030 冰岛人 (25 分)
坑点：
两个人维京人可能不是同辈的
需要一方搜到顶部，另一方搜
4
4
4 代以内的
因为可能搜到顶部的一方辈分更大，所以搜交换搜索顺序再搜一次就可以了
还有一个细节就是建边的时候只需要建维京人内部的就好了，不能涉及普通人
code：
#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define ld long double
#define all(x) x.begin(), x.end()
#define mem(x, d) memset(x, d, sizeof(x))
#define eps 1e-6
using namespace std;
const int maxn = 2e5 + 9;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll n, m;
map <pair<string, string>, int> ma;
/*
男
维京 n
普通 m
女 维京 r
普通 f
*/
map <string, int> id;
vector <int> v[maxn];
int cnt;
bitset <maxn> vis;
bool flag = 0;
void dfs1(int x, int dep){
vis[x] = 1;
for(auto to : v[x]){
dfs1(to, dep + 1);
}
}
void dfs2(int x, int dep){
if(dep > 4) return;
if(vis[x]) flag = 1;
for(auto to : v[x]){
dfs2(to, dep + 1);
}
}
void work()
{
cin >> n;
for(int i = 1; i <= n; ++i){
string a, b;cin >> a >> b;
string t = "";
if(b.back() == 'n'){
for(int i = 0; i < b.size() - 4; ++i) t += b[i];
ma[{a, t}] = 1;
}
else if(b.back() == 'm'){
for(int i = 0; i < b.size() - 1; ++i) t += b[i];
ma[{a, t}] = 1;
}
else if(b.back() == 'r'){
for(int i = 0; i < b.size() - 7; ++i) t += b[i];
ma[{a, t}] = 2;
}
else {
for(int i = 0; i < b.size() - 1; ++i) t += b[i];
ma[{a, t}] = 2;
}
if(!id.count(a)) id[a] = ++cnt;
if(!id.count(t)) id[t] = ++cnt;
if(b.back() == 'n' || b.back() == 'r')
v[id[a]].push_back(id[t]);
}
cin >> m;
while(m--){
string a, b, c, d;cin >> a >> b >> c >> d;
if(!ma.count({a, b}) || !ma.count({c, d})) cout << "NA\n";
else if(ma[{a, b}] == ma[{c, d}]) cout << "Whatever\n";
else {
flag = 0;
vis.reset();
dfs1(id[a], 1);
dfs2(id[c], 1);
if(!flag){
vis.reset();
dfs1(id[c], 1);
dfs2(id[a], 1);
}
cout << (flag ? "No" : "Yes") << endl;
}
}
}
int main()
{
ios::sync_with_stdio(0);
// int TT;cin>>TT;while(TT--)
work();
return 0;
}
