天梯試合決勝l 2-016天下の恋人がすべて長年離れ離れになった兄妹であることを望みます

タイトル:
ほほほ.五服以内は結婚できないことはよく知られています.つまり、二人の最近の共通の祖先が五代以内(本人、両親、祖父母、曽祖父母、高祖両親)であれば結婚できません.本題は、彼らが結婚できるかどうかを判断するカップルを助けてください.
入力形式:
最初の行に入力すると、正の整数N(2<=N<=104)が与えられ、その後、N行が与えられ、各行は以下の形式で1人の情報が与えられる.
本人ID性別父親ID母親ID
このうちIDは5桁の数字で、一人一人が違います.性別Mは男性、Fは女性を表す.ある人の父親や母親が試験を受けられなくなった場合、対応するID位置には-1とマークされます.
次に正の整数Kが与えられ、その後K行が与えられ、各行は恋人のIDのペアが与えられ、その間はスペースで区切られる.
注意:テーマは2人が同世代であることを保证して、1人1つの性别だけあって、しかも血縁関系のネットの中で母と息子の近親相姦あるいは隔世代の成婚の情况がありません.
出力フォーマット:
それぞれのカップルに恋人がいることに対して、彼らの関係が結婚できるかどうかを判断します:もし二人が同性であれば、「Never Mind」を出力します;異性で関係がある場合は「Yes」を出力します.異性関係が5服も出ていない場合は、「No」を出力します.サンプルを入力:
24 00001 M 01111 -1 00002 F 02222 03333 00003 M 02222 03333 00004 F 04444 03333 00005 M 04444 05555 00006 F 04444 05555 00007 F 06666 07777 00008 M 06666 07777 00009 M 00001 00002 00010 M 00003 00006 00011 F 00005 00007 00012 F 00008 08888 00013 F 00009 00011 00014 M 00010 09999 00015 M 00010 09999 00016 M 10000 00012 00017 F -1 00012 00018 F 11000 00013 00019 F 11100 00018 00020 F 00015 11110 00021 M 11100 00020 00022 M 00016 -1 00023 M 10012 00017 00024 M 00022 10013 9 00021 00024 00019 00024 00011 00012 00022 00018 00001 00004 00013 00016 00017 00015 00019 00021 00010 00011
出力サンプル:
Never Mind Yes Never Mind No Yes No Yes No No
2つの方法が解決できる:1.最初の5世代の祖先をマークし、2番目の5世代の祖先がマークされているかどうかを判断します.2.再帰して前の5世代に2人が同じ祖先を持っているかどうかを探す.最初はどちらも部分的に正しい方法しかなかったが、他の人の助けで発見されたのは--両親の性別は設定されていない!!!親も離婚できるし、恋人になれるし...
次の2つの方法のコード:1.再帰的に祖先を探す

#include
#include
using namespace std;
int mother[100000];
int father[100000];
//int numdai;
typedef struct
{
    char sex;
    int fa;
    int ma;
}Man;
Man man[100010];

int find(int a,int b,int num)
{
    if(a == -1 || b == -1)
        return 1;
    if((mother[a] != -1 && mother[a] == mother[b]) || (father[a] != -1 && father[a] == father[b]))
        return 0;
    num++;
    if(num >= 4)
        return 1;
    return (find(mother[a],mother[b],num) && find(father[a],father[b],num) && find(mother[a],father[b],num) && find(father[a],mother[b],num));
}

int main()
{
    memset(mother,-1,sizeof(mother));
    memset(father,-1,sizeof(father));
    int n;
    cin>>n;

    for(int i=0;iint a;
        cin>>a;
        cin>>man[a].sex>>man[a].fa>>man[a].ma;
        if(man[a].fa != -1)
        {
            father[a] = man[a].fa;
            man[man[a].fa].sex = 'M';
        }   
        if(man[a].ma != -1)
        {
            mother[a] = man[a].ma;
            man[man[a].ma].sex = 'F';
        }

        if(man[a].fa == -1)
            father[a] = -1;
        if(man[a].ma == -1)
            mother[a] = -1;
    }

    int m;
    cin>>m;

    for(int i=0;iint a,b;
        cin>>a>>b;

        if(man[a].sex == man[b].sex)
            cout<<"Never Mind"<else
        {
            int numdai=0;
            if(find(a,b,numdai))
                cout<<"Yes"<else
                cout<<"No"<return 0;
}

2.タグ方式:

#include
#include
#include
using namespace std;
int mother[100000+1];
int father[100000+1];
int visited[100000+1];
typedef struct
{
  char sex;
  int fa;
  int ma;
}Man;
Man man[100010];

void find(int a)
{
  int num=0;
  queue<int> q;
  q.push(a);

  while(!q.empty())
  {
    int now = q.front();
    q.pop();

    if(num >=30)
      break;

    if(now != -1 && mother[now+1] != -1) 
      visited[mother[now+1]] = 1;
    if(now != -1 && father[now+1] != -1) 
      visited[father[now+1]] = 1;
    q.push(mother[now+1]);
    q.push(father[now+1]);
    num+=2;
  }
}

int find2(int a)
{
  int num=0;
  queue<int> q;
  q.push(a);

  while(!q.empty())
  {
    int now = q.front();
    q.pop();

    if(num >=30)
      break;

    if(now != -1 && mother[now+1] != -1 && visited[mother[now+1]] == 1) 
      return 0;
    if(now != -1 && father[now+1] != -1 && visited[father[now+1]] == 1) 
      return 0;
    q.push(mother[now+1]);
    q.push(father[now+1]);
    num+=2;
  }
  return 1;
}

int main()
{
  memset(mother,-1,sizeof(mother));
  memset(father,-1,sizeof(father));
  int n;
  cin>>n;

  for(int i=0;iint a;
    cin>>a;
    cin>>man[a].sex>>man[a].fa>>man[a].ma;
    if(man[a].fa != -1)
    {
        father[a+1] = man[a].fa;
        man[man[a].fa].sex = 'M';
    }

    if(man[a].ma != -1)
    {
        mother[a+1] = man[a].ma;
        man[man[a].ma].sex = 'F';
    }

    if(man[a].fa == -1)
      father[a+1] = -1;
    if(man[a].ma == -1)
      mother[a+1] = -1;
  }

  int m;
  cin>>m;

  for(int i=0;imemset(visited,0,sizeof(visited));
    int a,b;
    cin>>a>>b;

    if(man[a].sex == man[b].sex)
      cout<<"Never Mind"<else
    {
      int numdai=0;
      find(a);
      if(find2(b))
        cout<<"Yes"<else
        cout<<"No"<return 0;
}